Problem E. 逃离机场
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 269 Accepted Submission(s): 52
Problem Description
小明听说机场是一个很肥的地方，所以想跳一波机场，看看到底有多肥。不过机场虽然肥，但是跳的人也多。小明第一次跳机场，刚跳下来就到处都是枪声，小明吓得快要哭出来了，想逃离机场，emmm，还是打野比较适合他。
现在把机场看作一个二维平面，’.’ 代表可以走的空地，’@’代表小明当前的位置，’x’代表这里是个障碍物，’o’代表这里有个敌人，并且手里有枪，敌人可以攻击上下左右四个方向，小明只要走到或者一开始就在敌人可以攻击的位置，就会死亡（机场个个都是98K爆头dalao)，子弹不会穿过障碍物，敌人不会移动。小明只能往上下左右走，每走一步需要1秒，只要小明移动到机场的边缘再走一步就算逃离了机场，现在小明请你帮他找一条最快逃离机场的线路，输出这个时间，如果怎么都逃不出去，输出”no zuo no die!”（不含引号）。
Input
多组测试数据，首先第一行一个整数T，代表测试数据组数。1≤T≤100。
每组测试数据有n,m(1≤n,m≤200)，代表机场是一个n×m的方阵，接下来是一个由’.’，’@’，’x’，’o’构成的n×m的方阵，’@’只有一个。
Output
对于每组数据输出一个数代表最快需要多少时间逃出机场，或者”nozuonodie!”。
Sample Input
3
5 5
.x.x.
.x.x.
.....
..@..
.o.o.
3 3
@..
xxx
o.x
3 3
o.o
.@.
.x.
Sample Output
4
1
no zuo no die!
解题思路：
1、走迷宫最短路（BFS）。
2、敌人一开始初始化成墙，但是需要注意：敌人替换成的这个“墙”不会阻碍其他敌人的“墙”（可以穿透）。
AC 代码
/
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int n,m; const int dir[4][2]={1,0,-1,0,0,1,0,-1}; // UDRL:(i from 0 to 3) struct node { int x,y,sp; }; node nd_s; char g[300][300]; void fillMaze(int x,int y,int &flag) { g[x][y]='#'; for(int i=x-1;i>=0;i--) { if(g[i][y]!='.') { if(g[i][y]=='@') flag=1; else if(g[i][y]=='#') continue; break; } else if(g[i][y]=='.') g[i][y]='#'; } for(int i=x+1;i<n;i++) { if(g[i][y]!='.') { if(g[i][y]=='@') flag=1; else if(g[i][y]=='#') continue; break; } else if(g[i][y]=='.') g[i][y]='#'; } for(int j=y-1;j>=0;j--) { if(g[x][j]!='.') { if(g[x][j]=='@') flag=1; else if(g[x][j]=='#') continue; break; } else if(g[x][j]=='.') g[x][j]='#'; } for(int j=y+1;j<m;j++) { if(g[x][j]!='.') { if(g[x][j]=='@') flag=1; else if(g[x][j]=='#') continue; break; } else if(g[x][j]=='.') g[x][j]='#'; } } int mazeBfs(node s) { queue<node> tp; node u,t; g[s.x][s.y]='x'; tp.push(s); while(!tp.empty()) { u=tp.front(); tp.pop(); if(u.x+1>=n || u.x-1<0 || u.y+1>=m || u.y-1<0) return 1+u.sp; for(int i=0;i<4;i++) { t.x=u.x+dir[i][0]; t.y=u.y+dir[i][1]; if(g[t.x][t.y]=='.') { t.sp=u.sp+1; g[t.x][t.y]='x'; tp.push(t); } } } return -1; } //void showG() //{ // puts("----------------"); // for(int i=0;i<n;i++) // { // for(int j=0;j<m;j++) // { // printf("%c ",g[i][j]); // } // puts(""); // } // puts("----------------"); //} int main() { int T; scanf("%d",&T); string s; while(T-- && ~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) scanf("%s",g[i]); int flag=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if('@'==g[i][j]) nd_s.x=i, nd_s.y=j, nd_s.sp=0; else if('o'==g[i][j]) fillMaze(i,j,flag); } } // showG(); if(flag==1) puts("no zuo no die!"); else { int rs=mazeBfs(nd_s); if(rs==-1) puts("no zuo no die!"); else printf("%d\n",rs); } } return 0; }
![[SDUT 2414] | 山东省第三届省赛 An interesting game | 最小费用最大流](https://ucc.alicdn.com/pic/developer-ecology/1683b30416874c8cbffd8b7764f03993.png?x-oss-process=image/resize,h_160,m_lfit)