bfs水题,刚开始以为必须要杀死敌人,wa了一次
code:
/* ID: yueqiq PROG: numtri LANG: C++ */ #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) const int maxn = 101; const int INF = 1111; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; const double pi = acos(-1.0); const double eps= 1e-7; using namespace std; int N,M; int sx,sy,ex,ey; struct node{ int x,y,times; }; char Map[maxn][maxn]; bool vis[maxn][maxn]; //bool flag; int bfs(){ node tmp,cur; queue<node> q; cur.x=sx; cur.y=sy; cur.times=0; vis[sx][sy]=1; q.push(cur); while(!q.empty()){ tmp=q.front(); //printf("the pop x:%d y:%d time:%d\n",tmp.x,tmp.y,tmp.times); q.pop(); if(tmp.x==ex && tmp.y==ey) return tmp.times; FF(i,4){ cur.x=tmp.x+dx[i]; cur.y=tmp.y+dy[i]; cur.times=tmp.times+1; if(cur.x>0&&cur.y>0&&cur.x<=N&&cur.y<=M&&!vis[cur.x][cur.y]){ if(Map[cur.x][cur.y]=='.'){ vis[cur.x][cur.y]=1; // printf("x:%d y:%d time:%d\n",cur.x,cur.y,cur.times); q.push(cur); } if(Map[cur.x][cur.y]=='x'){ vis[cur.x][cur.y]=1; cur.times++; //flag=true; // printf("x:%d y:%d time:%d !!!\n",cur.x,cur.y,cur.times); q.push(cur); } if(Map[cur.x][cur.y]=='a'){ vis[cur.x][cur.y]=1; //printf("aaa x:%d y:%d time:%d\n",cur.x,cur.y,cur.times); q.push(cur); } } } } return -1; } int main() { while(~scanf("%d%d",&N,&M)){ SET(vis,false);//flag=false; FOR(i,1,N) FOR(j,1,M){ scanf(" %c",&Map[i][j]); if(Map[i][j]=='r'){ sx=i;sy=j; } if(Map[i][j]=='a'){ ex=i;ey=j; } } //printf("%d %d \n",sx,sy); int k=bfs(); if( k==-1 ) printf("Poor ANGEL has to stay in the prison all his life."); else PD(k);LN; } return 0; }