Ignatius and the Princess I

  1 //0MS    1688K    1977B    G++
  2 #include<iostream>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<string.h>
  6 
  7 using namespace std;
  8 const int MAXN = 0xffffff;
  9 
 10 struct Node{
 11     int x;
 12     int y;
 13     int step;
 14     char c;
 15 };
 16 int n,m, ans;
 17 int mov[4][2]={0,1,1,0,0,-1,-1,0};
 18 int nxt[105][105];
 19 int map[105][105];
 20 char g[105][105];
 21 
 22 void bfs(int sx, int sy)
 23 {
 24     queue<Node>Q;
 25     Node node;
 26     if(g[sx][sy] != ‘X‘){    
 27         node.x=sx;
 28         node.y=sy;
 29         node.step=0;
 30         node.c = g[sx][sy];
 31         Q.push(node);
 32         map[sx][sy]=-1;
 33     }
 34     while(!Q.empty()){
 35         node = Q.front();
 36         Q.pop();
 37         if(node.x == n-1 && node.y==m-1){
 38             if(ans > node.step){
 39                 ans = node.step + ((g[node.x][node.y]==‘.‘)?0:(g[node.x][node.y]-‘0‘));
 40             }
 41             break;
 42         }
 43         node.step += 1;
 44 
 45         if(node.c != ‘.‘ && node.c != ‘0‘){
 46             node.c -= 1;
 47             Q.push(node);
 48             continue;
 49         }
 50         for(int i=0;i<4;i++){
 51             int tx = node.x + mov[i][0];
 52             int ty = node.y + mov[i][1];
 53 
 54             if(tx>=0 && tx<n && ty>=0 && ty<m && g[tx][ty]!=‘X‘ && map[tx][ty]!=-1){
 55                 Node tnode = {tx, ty, node.step, g[tx][ty]};
 56                 Q.push(tnode);
 57                 map[tx][ty] = -1;
 58                 nxt[tx][ty] = i;
 59             }
 60         }
 61     }
 62 }
 63 
 64 void print(int x, int y, int sec)
 65 {
 66     
 67     if(sec <= 0) return;
 68     int id = nxt[x][y];
 69     
 70     int use = (g[x][y]==‘.‘)?0:(g[x][y]-‘0‘);
 71     print(x-mov[id][0], y-mov[id][1], sec-1-use);
 72     
 73     if(sec- use > 0)
 74         printf("%ds:(%d,%d)->(%d,%d)\n", sec-use, x-mov[id][0], y-mov[id][1], x, y);
 75     if(g[x][y]!=‘X‘){
 76         for(int i=use-1;i>=0;i--){
 77             printf("%ds:FIGHT AT (%d,%d)\n", sec-i, x, y);
 78         }
 79     }
 80         
 81 }
 82 
 83 int main()
 84 {
 85     while(scanf("%d%d",&n,&m)!=EOF){
 86         
 87         for(int i=0;i<n;i++){
 88             scanf("%s", &g[i]);    
 89         }
 90         
 91         memset(map, 0, sizeof(map));
 92         memset(nxt, 0, sizeof(nxt));
 93         ans = MAXN;
 94         bfs(0, 0);
 95         
 96         if(ans != MAXN){
 97             printf("It takes %d seconds to reach the target position, let me show you the way.\n", ans);
 98             print(n-1, m-1, ans);
 99         }else{
100             puts("God please help our poor hero.");
101         }
102         puts("FINISH");
103     }
104     return 0;    
105 }