生化武器（BFS）

生化武器查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb在一个封闭的房间里gogo给大家表演了他的屁遁术人果然一下没影了但是他留下的“生化武器”却以每秒1米的速度向上下左右扩散出去。为了知道自己会不会被“毒”到你果断写了个算法计算出了“毒气”在t秒时间内可以到达的所有地方。输入输出格式输入描述:有多组测试数据 第一行输入n,m,t0n,m30 n和m表示图的行和列t表示时间 ‘*’为表演的地点‘X’是墙‘.’为空白的地方输出描述:如果在t秒时间内毒气没有充满房间或刚好充满输出现在房间里的情况‘#’表示有‘毒气’的地方 否则输出“No” 每组数据输出后有一个空行输入输出样例输入样例#:复制9 9 4 XXXXXXXXX X...X...X X.*.....X X...X...X XXXXXXXXX X...X X...X X...X XXXXX 5 5 2 XXXXX X...X X.*.X X...X XXXXX输出样例#:复制XXXXXXXXX X###X#..X X######.X X###X#..X XXXXXXXXX X...X X...X X...X XXXXX XXXXX X###X X###X X###X XXXXX#includebits/stdc.h using namespace std; char g[35][35]; int dist[35][35]; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; int main(){ int n, m, t; while(cinnmt){ int row -1, col -1;//初试为止 // for(int i 0; i n; i ){//!!!!!!!!有空格不能这样输入 // for(int j 0; j m; j ){ // dist[i][j] -1;//标记为-1 // // cing[i][j];//输入迷 // if(g[i][j] *){//七点 // row i; // col j; // } // } // } for(int i 0; i n; i ){//整行扫描 string s; cins; for(int j 0; j m; j ){ dist[i][j] -1; g[i][j] s[j]; if(s[j] *){ row i; col j; } } } queuepairint, intq; q.push({row, col}); dist[row][col] 0;//初试距离 g[row][col] #; int temp 0;//计时 !!!!!!!不需要这个来判断是否应该结束 bool full true; while(!q.empty()){ // if(temp t){//时间到了 // break; // } auto it q.front();//当前位置 q.pop();//记得出队 int row0 it.first; int col0 it.second; temp max(temp, dist[row0][col0]);//扩散一次时间1 不要乱加 if(dist[row0][col0] t){//时间到了 break; } for(int i 0; i 4; i ){ int row1 row0 dx[i]; int col1 col0 dy[i]; if(row1 n || row1 0 || col1 m || col1 0){//过线了 continue; } if(g[row1][col1] X || g[row1][col1] #){//撞墙或去过 continue; } if(dist[row1][col1] ! -1){//去过 continue; } dist[row1][col1] dist[row0][col0] 1; g[row1][col1] #;//标记去过 q.push({row1, col1}); } } for(int i 0; i n; i ){ for(int j 0; j m; j ){ if(g[i][j] .){//没有充满 full false; break; } } } if(full temp t){//看清题目要求 coutNoendl; } else{ for(int i 0; i n; i ){ for(int j 0; j m; j ){ coutg[i][j]; } coutendl; } } coutendl; } }