这题的题意简单来说就是“找出起点附近最大的连续黑色区块“
因此我利用BFS寻找最多可以走几步的想法来计算它
（不知道这题用DFS会不会比较快>"<
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<iostream> | |
| #include<cstdio> | |
| #include<queue> | |
| using namespace std; | |
| int p[101][101],times; | |
| typedef pair<int,int> Point;//存入坐标 | |
| int xt[4] = {-1, 1, 0, 0};//前后左右寻找 | |
| int yt[4] = { 0, 0, 1,-1}; | |
| int BFS(int x,int y){ | |
| queue <Point> Queue;//建立queue | |
| Queue.push(make_pair(x,y));//将起点push进去 | |
| times = 1;//步数设为1 | |
| while(!Queue.empty()){//若queue为零 则跳出回圈 | |
| Point now = Queue.front(); | |
| int r = now.first,c = now.second; | |
| Queue.pop(); | |
| for(int i=0;i<4;i++){ | |
| int tx,ty; | |
| tx = r+xt[i]; | |
| ty = c+yt[i]; | |
| if(p[tx][ty]==1){ | |
| Queue.push(make_pair(tx,ty)); | |
| p[tx][ty] = -1;//将走过的点作记号 | |
| times++; | |
| } | |
| } | |
| } | |
| return times;//回传步数 | |
| } | |
| int main(){ | |
| int N,M,x,y; | |
| char ch; | |
| while(scanf("%d %d",&N,&M)&&(M||N)){//读入空间大小 | |
| for(int i=0;i<=M+1;i++){ | |
| for(int j=0;j<=N+1;j++){ | |
| if(i==0||i == M+1||j==0||j==N+1) p[i][j] = 0;//将边界设为不能走 | |
| else{ | |
| cin>>ch; | |
| if(ch == '.') p[i][j] = 1;//黑色空格设为1 代表可以走 | |
| if(ch == '#') p[i][j] = 0;//红色空格设为0 代表不能走 | |
| if(ch == '@') {p[i][j] = -1;x = i;y = j;}//将起点记录起来 | |
| } | |
| } | |
| } | |
| //开始BFS广度搜寻 | |
| cout<<BFS(x,y)<<endl; | |
| } | |
| } |
沒有留言:
張貼留言
注意：只有此網誌的成員可以留言。