Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19343 Accepted Submission(s): 11764PRoblem DescriptionThere 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. InputThe 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) OutputFor 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 Output4559613 SourceAsia 2004, Ehime (Japan), Japan Domestic基础的搜索问题，需要注意的一点就是，跟以往不同，这里每行所给的两个数分别是列数和行数。#include<stdio.h>#include<string.h>int a,b;int to[4][2]={-1,0,0,-1,1,0,0,1};//所能走的四个方向int visit[20][20];char map[20][20];int sum;int dfs(int x,int y){ int ex,ey; int i; for(i=0;i<4;i++) { ex=x+to[i][0]; ey=y+to[i][1]; if(map[ex][ey]=='.'&&ex>=0&&ey>=0&&ex<b&&ey<a&&visit[ex][ey]==0) { visit[ex][ey]=1; sum++; dfs(ex,ey); } }}int main(){ while(scanf("%d %d",&a,&b),a!=0||b!=0) { getchar(); int i,j; int x,y; for(i=0;i<b;i++) { for(j=0;j<a;j++) { scanf("%c",&map[i][j]); if(map[i][j]=='@') { x=i; y=j; } } getchar(); } memset(visit,0,sizeof(visit)); sum=1; dfs(x,y); printf("%d/n",sum); } return 0;}
新闻热点
疑难解答
