123

#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <utility> using namespace std; int r,c; int map[1010][1010]; int time[1010][1010]; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; queue< pair<int,int> > J; //声明方式 queue< pair<int,int> > F; void print() { int i,j; for(i = 0; i < r+1; i++) { for(j = 0; j<c+1; j++) { printf("%d ",time[i][j]); } printf("\n"); } printf("\n"); } void bfs_fire() { pair<int, int> FF; int t, i, x, y; while( !F.empty() ) { FF = F.front(); F.pop(); t = time[FF.first][FF.second]; for( i = 0; i < 4; i++) { x = FF.first + dir[i][0]; y = FF.second + dir[i][1]; if(x >= r || x < 0 || y >= c || y < 0)//越界 continue; if( time[x][y] == 0 ) { time[x][y] = t + 1; F.push(make_pair(x, y)); } } } } void bfs_people() { pair<int,int> JJ; int t, i, x, y, ok = 0; while( !J.empty() ) { JJ = J.front(); J.pop(); t = map[JJ.first][JJ.second]; map[JJ.first][JJ.second] = -1;//标记访问(把这个地方变成墙就行) for( i = 0; i < 4; i++)//向四个方向扩展(能走的) { x = JJ.first + dir[i][0]; y = JJ.second + dir[i][1]; //pair 具有 first 与 second 成员 if(x >= r || x < 0 || y >= c || y < 0)//越界 continue; if( map[x][y] == -1 || map[x][y] <= time)//墙或超时 continue; else if( x == r - 1 || x == 0 || y == 0 || y == c - 1 )//边界则走完 { ok = 1; printf("%d\n", time); return; } else { J.push(make_pair(x, y));//queue中插入pair 利用make_pair()方法 } } } if(ok == 0) printf("IMPOSSIBLE\n"); } */ int main() { int N; int i,j; char temp; freopen("1.txt", "r", stdin); scanf("%d", &N); getchar(); while(N--) { while( !J.empty() ) J.pop(); //注意初始化(清空)队列 while( !F.empty() ) F.pop(); memset(map, -1, sizeof(map)); memset(time, -1, sizeof(time)); scanf("%d%d", &r, &c); getchar(); for(i = 0; i < r; i++) { for(j = 0; j < c; j++) {//# = -1 F = 1 . = 0 scanf("%c", &temp);//当读取%c时，注意用getchar吸收掉不必要的回车 if(temp == '#'){map[i][j] = time[i][j] = -1;} else if(temp == 'F'){map[i][j] = time[i][j] = 1;F.push(make_pair(i,j));} else if(temp == 'J'){map[i][j] = 1;time[i][j] = 0;J.push(make_pair(i,j));} else{map[i][j] = time[i][j] = 0;} } getchar(); } bfs_fire(); // bfs_people(); } return 0; }

 

转载于:https://www.cnblogs.com/wwjyt/p/3154124.html

相关资源：数据结构—成绩单生成器