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.有且只有一个结点没有双亲结点,这个结点称为根结点    2.根以外的其它结点有且只有一个双亲结点其实层次数据模型就是的图形表示就是一个倒立生长的树,由基本数据结构中的树(或者二叉树)的定义可知,每棵树都有且仅有一个根节点,其余的…

    2022年10月29日
  • oracle 查看所有表和视图

    oracle 查看所有表和视图查看所有表:select*fromall_tables查看所有视图:select*fromall_views

  • css opacity属性_CSS中的opacity属性[通俗易懂]

    css opacity属性_CSS中的opacity属性[通俗易懂]cssopacity属性CSS|不透明度属性(CSS|opacityProperty)Withthegrowingneedofmakingwebsites,theneedforstylingthemhasalsoincreased.Therefore,CSShasbecomeanindispensablepartofcreating…

  • Vagrant 基本使用操作

    Vagrant 基本使用操作OthersVagrant基本使用操作Vagrant是什么?Vagrant安装Vagrant快速上手安装CentOSVagrant基本命令小结Vagrantfile文件Vagrant基本使用操作Vagrant是什么?Vagrant是一款支持自动化虚拟机暗转、可配置流程的用于管理虚拟机的软件.主要的优势在于可以提供一个可配置、可移植和复用的虚拟机环境(通过定义Vagr…

    2022年10月25日
  • 基于UDP编程_udp详解

    基于UDP编程_udp详解基于UDP编程1UDP是数据报协议,无连接的,不可靠,追求传输效率的一种通信协议数据的发送和接收是同步的.在进行通信之前,不需要建立连接.其传输效率比TCP高.对其服务器而言,并没有三次握手的过程.因此和TCP相比,少了被动监听(listen)和(accept).只需要创建通信设备,绑定IP地址和端口号.然后进行数据的收发.1.服务器端的编程模型创建一个socket端点,返回该端点的文件描述符fdsocket(2)2)将fd和本地地址绑定bind(2)while(1){3)阻塞等待

  • mysql b+树优点_基础B

    mysql b+树优点_基础B写在前面大家在面试的时候,肯定都会被问到MySql的知识,以下是面试场景:面试官:对于MySQL,你对他索引原理了解吗?我:了解面试官:MySQL的索引是用什么数据机构的?我:B+树面试官:为什么要用B+树,而不是B树?我:…面试官:用B+树作为MySql的索引结构,用什么好处?我:…B树和B+树是MySQL索引使用的数据结构,对于索引优化和原理理解都非常重要,下面我的写文章就是要把B树,B+树的神秘面纱揭开,让大家在面试的时候碰到这个知识点一往无前,不再成为你的知识盲点!欢迎关注公

发表回复

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

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