链接:http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4998
题意:就是人朝四个方向移动,只能走黑色瓷砖,红色瓷砖不能走,求人能走多少块瓷砖。
思路:W表示列数,H表示行数,一开始没注意,拿W当行数了,结果很郁闷。以后审题能不能仔细点!方法就是直接搜,从起点开始,遇到红瓷砖,超过边界的或者已经搜过的就不搜了,符合条件的瓷砖就cnt++,比较简单,不用清理现场。
#include<iostream> #include<cstdio> #include<cstring> #include<map> using namespace std; const int maxn=22; char grid[maxn][maxn]; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; int visited[maxn][maxn]; int W,H,cnt; void dfs(int x,int y) { visited[x][y]=1; int xx,yy; for(int i=0;i<4;i++) { xx=x+dir[i][0];yy=y+dir[i][1]; if(xx<0 || xx>=H || yy<0 || yy>=W) continue; if(grid[xx][yy]=='#') continue; if(visited[xx][yy]) continue; cnt++; dfs(xx,yy); } } int main() { int si,sj; while(scanf("%d%d",&W,&H) && W && H) { getchar(); cnt=1; memset(visited,0,sizeof(visited)); for(int i=0;i<H;i++) { for(int j=0;j<W;j++) { scanf("%c",&grid[i][j]); if(grid[i][j]=='@') { si=i;sj=j; } } getchar(); } dfs(si,sj); printf("%d\n",cnt); } return 0; }
还是内伤。。。不想说了。。。