POJ 1979 Red and Black

POJ 1979 Red and Black

Red and Black
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 21482   Accepted: 11488

Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles. 

Write a program to count the number of black tiles which he can reach by repeating the moves described above. 

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20. 

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows. 

‘.’ – a black tile 

‘#’ – a red tile 

‘@’ – a man on a black tile(appears exactly once in a data set) 

The end of the input is indicated by a line consisting of two zeros. 

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

Sample Output

45
59
6
13

Source

思路 :简单的深搜
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int r,c;
char a[200][200];
int vis[200][200];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int sum;

void dfs(int i,int j)
{
             
  //if(a[i][j]=='#'||(vis[i][j])||(i<0||j<0||(i>r-1||j>c-1)))
  //return;
  //else 
  //{
      a[i][j]='#';  
      sum++;                                           
  for(int k = 0;k < 4;k++)
  {
         int x = i+dir[k][0];
         int y = j+dir[k][1];
         if(a[x][y]=='.'&&!vis[x][y]&&x>=0&&y>=0&&x<=r-1&&y<=c-1)  
        {
           dfs(x,y);
           vis[x][y]=1;
         }
  } 
  //} 
  
  
}
int main()
{
   int i,j,x,y;
   while(scanf("%d%d",&c,&r),r||c) 
   { 
          sum=0;
          memset(vis,0,sizeof(vis));
          memset(a,0,sizeof(a));
                                   
      for(i=0;i<r;i++)
      {
           getchar();
        for(j=0;j<c;j++)
        {
             a[i][j] = getchar();
             if(a[i][j]=='@')
             {
                x=i;
                y=j;                
             }          
        }
       } 
       //count=0;
       dfs(x,y); 
       cout<<sum<<endl;                               
   }         
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119108.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 行为识别综述

    行为识别综述定义背景难点最新论文最新算法数据集1定义行为识别:行为识别(ActionRecognition)任务是从视频剪辑(2D帧序列)中识别不同的动作,其中动作可以在视频的整个持续时间内执行或不执行。行为识别似乎是图像分类任务到多个帧的扩展,然后聚合来自每帧的预测。尽管图像分类取得了很大的成功,但是视频分类和表示学习依然进展缓慢。2背景2.1方法2.1.1传统方法提取视频区域的局部高维视觉特征,然后组合成固定大小的视频级描述,最后利用分类器(SVM,RF等)进行最终预测2.

  • webservice示例

    webservice示例webservice示例:webservice是什么:WebService是一种跨编程语言和跨操作系统平台的远程调用技术。所谓跨编程语言和跨操作平台,就是说服务端程序采用java编写,客户端程序

  • 微信小程序开发实战1 微信小程序开发概述

    微信小程序开发实战1 微信小程序开发概述1.微信小程序开发概述1.1微信小程序的特点微信小程序是微信平台提供的一种开放技术,微信小程序为企业用户服务,用于建立一种移动端的“轻应用”,这种应用是不需要下载安装即可使用的应用,用户扫一扫或者搜一下即可打开应用。用户也不用关心是否安装了太多应用的而造成手机空间不足问题。微信小程序的推出后,与订阅号、服务号、企业号并列成为微信的企业应用体系。图1-1微信公众平台产品类型微信小程序运行在微信平台之上,微信平台对不同的手机平台已经做了兼容。使用微信小程序开发的应用,不需要兼容多个平台,开发完成后可

  • c语言解析xml文件「建议收藏」

    c语言解析xml文件「建议收藏」#include”stdafx.h”#include#include”Mytext.h”#include#include#include#include#include#include#include#include#include#includeusingnamespacestd;#pragmacomment(lib,”Oleac

  • SpringBoot 介绍「建议收藏」

    SpringBoot 介绍「建议收藏」SpringBoot介绍目录1.简介2.WhySpringBoot1.简介    SpringBoot最开始基于Spring4.0设计,是由Pivotal公司提供的框架。    SpringBoot发展史:2003年RodJohnson成立Interface公司,产品是SpringFramework2004年,Spring框架开源,公司改名为SpringSource2008年,收购ApacheSer

  • TypeScript基础入门之Javascript文件类型检查(二)「建议收藏」

    TypeScript基础入门之Javascript文件类型检查(二)「建议收藏」TypeScript基础入门之Javascript文件类型检查(二)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号