poj 1475 Pushing Boxes

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <string.h>
  5 #include <string>
  6 #include <math.h>
  7 #include <stdlib.h>
  8 #include <queue>
  9 #include <stack>
 10 #include <set>
 11 #include <map>
 12 #include <list>
 13 #include <iomanip>
 14 #include <vector>
 15 #pragma comment(linker, "/STACK:1024000000,1024000000")
 16 #pragma warning(disable:4786)
 17 
 18 using namespace std;
 19 
 20 const int INF = 0x3f3f3f3f;
 21 const int MAX = 20 + 2;
 22 const double eps = 1e-8;
 23 const double PI = acos(-1.0);
 24 
 25 char ma[MAX][MAX];
 26 int vis[MAX][MAX];
 27 int n , m;
 28 int si , sj , bi , bj , ti , tj , ei , ej;
 29 int dir[4][2] = {1 , 0 , -1 , 0 , 0 , 1 , 0 , -1};
 30 char path[4] = {‘S‘ , ‘N‘ , ‘E‘ , ‘W‘};
 31 char path1[4] = {‘s‘ , ‘n‘ , ‘e‘ , ‘w‘};
 32 string str , str1 , ans;
 33 
 34 struct T
 35 {
 36     int x , y ;
 37     string sss;
 38 }temp , in , out;
 39 
 40 queue<T>qq , qq1;
 41 
 42 void bfs(int i , int j)
 43 {
 44     temp.x = i;
 45     temp.y = j;
 46     temp.sss = "";
 47     qq.push(temp);
 48     vis[i][j] = 1;
 49     while(!qq.empty())
 50     {
 51         out = qq.front();
 52         qq.pop();
 53         if(out.x == ti && out.y == tj)
 54         {
 55             str = out.sss;
 56             break;
 57         }
 58         for(int k = 0;k < 4;k ++)
 59         {
 60             int ix = out.x + dir[k][0];
 61             int iy = out.y + dir[k][1];
 62             if(ma[ix][iy] == ‘#‘ || vis[ix][iy] || ix < 1 || iy < 1 || ix > n || iy > m)
 63                 continue;
 64             in.x = ix;
 65             in.y = iy;
 66             in.sss = out.sss + path[k];
 67             vis[ix][iy] = 1;
 68             qq.push(in);
 69         }
 70     }
 71 }
 72 
 73 void bfs1(int i , int j)
 74 {
 75     temp.x = i;
 76     temp.y = j;
 77     temp.sss = "";
 78     qq.push(temp);
 79     vis[i][j] = 1;
 80     while(!qq.empty())
 81     {
 82         out = qq.front();
 83         qq.pop();
 84         if(out.x == ei && out.y == ej)
 85         {
 86             str1 = out.sss;
 87             break;
 88         }
 89         for(int k = 0;k < 4;k ++)
 90         {
 91             int ix = out.x + dir[k][0];
 92             int iy = out.y + dir[k][1];
 93             if(ma[ix][iy] == ‘#‘ || ma[ix][iy] == ‘B‘ || vis[ix][iy] || ix < 1 || iy < 1 || ix > n || iy > m)
 94                 continue;
 95             in.x = ix;
 96             in.y = iy;
 97             in.sss = out.sss + path1[k];
 98             vis[ix][iy] = 1;
 99             qq.push(in);
100         }
101     }
102 }
103 
104 int main()
105 {
106     int first = 1;
107     while(scanf("%d %d",&n , &m) , n + m)
108     {
109         int i , j;
110         memset(vis , 0 , sizeof(vis));
111         for(i = 1;i <= n;i ++)
112         {
113             for(j = 1;j <= m;j ++)
114             {
115                 scanf("%c",&ma[i][j]);
116                 if(ma[i][j] == ‘S‘)
117                 {
118                     si = i;
119                     sj = j;
120                 }
121                 else if(ma[i][j] == ‘B‘)
122                 {
123                     bi = i;
124                     bj = j;
125                 }
126                 else if(ma[i][j] == ‘T‘)
127                 {
128                     ti = i;
129                     tj = j;
130                 }
131             }
132             getchar();
133         }
134         str = "";
135         while(!qq.empty())
136             qq.pop();
137         bfs(bi , bj);
138         if(str[0] == ‘S‘)
139         {
140             ei = bi - 1;
141             ej = bj;
142         }
143         else if(str[0] == ‘N‘)
144         {
145             ei = bi + 1;
146             ej = bj;
147         }
148         else if(str[0] == ‘E‘)
149         {
150             ei = bi;
151             ej = bj - 1;
152         }
153         else if(str[0] == ‘W‘)
154         {
155             ei = bi;
156             ej = bj + 1;
157         }
158 
159         memset(vis , 0 , sizeof(vis));
160         str1 = "";
161         while(!qq.empty())
162             qq.pop();
163         bfs1(si , sj);
164         ans = "";
165         ans = str1 + str;
166 
167         printf("Maze #%d\n",first ++);
168         if(ans != "")
169             cout << ans << "\n" << endl;
170         else
171             cout << "Impossible\n" << endl;
172     }
173     return 0;
174 }

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <string>
  7 
  8 using namespace std;
  9 
 10 #define MAXN 22
 11 char P[4]={‘N‘,‘S‘,‘W‘,‘E‘};
 12 char M[4]={‘n‘,‘s‘,‘w‘,‘e‘};
 13 int R,C;
 14 int dir[4][2]={-1,0,1,0,0,-1,0,1};
 15 char map[MAXN][MAXN];
 16 struct point
 17 {
 18     int x,y;
 19     int p_x,p_y;//当前状态person所在的地方
 20     string ans;
 21 };
 22 bool isok(int x,int y)
 23 {
 24     if(x>=0 && x<R && y>=0 && y<C && map[x][y] != ‘#‘)
 25         return true;
 26     return false;
 27 }
 28 string tmp;
 29 bool bfs_person(point en,point cu)
 30 {
 31     tmp="";
 32     point st;
 33     st.x=en.p_x;
 34     st.y=en.p_y;
 35     st.ans="";
 36     queue<point>q;
 37     bool vis[MAXN][MAXN];
 38     memset(vis,0,sizeof(vis));
 39     while(!q.empty())
 40         q.pop();
 41     q.push(st);
 42     while(!q.empty())
 43     {
 44         point cur,next;
 45         cur=q.front();
 46         q.pop();
 47         if(cur.x==en.x && cur.y==en.y)
 48         {
 49             tmp=cur.ans;
 50             return true;
 51         }
 52         for(int i=0;i<4;i++)
 53         {
 54             next=cur;
 55             next.x=cur.x+dir[i][0];
 56             next.y=cur.y+dir[i][1];
 57             if(!isok(next.x,next.y)) continue;
 58             if(next.x==cu.x && next.y==cu.y) continue;
 59             if(vis[next.x][next.y]) continue;
 60             vis[next.x][next.y]=1;
 61             next.ans=cur.ans+M[i];
 62             q.push(next);
 63         }
 64     }
 65     return false;
 66 }
 67 string bfs_box()
 68 {
 69     bool vis[MAXN][MAXN][4];//某点四个方向是否访问！！0==N,1==S,2==W,3==E
 70     point st;
 71     st.x=st.y=-1;
 72     st.p_x=st.p_y=-1;
 73     st.ans="";
 74     for(int i=0;i<R && (st.x==-1 || st.p_x==-1);i++)
 75         for(int j=0;j<C && (st.x==-1 || st.p_x==-1);j++)
 76             if(map[i][j]==‘B‘)
 77             {
 78                 st.x=i;
 79                 st.y=j;
 80                 map[i][j]=‘.‘;
 81             }
 82             else if(map[i][j]==‘S‘)
 83             {
 84                 st.p_x=i;
 85                 st.p_y=j;
 86                 map[i][j]=‘.‘;
 87             }
 88     //----------------------------------------
 89     //cout<<"st.x="<<st.x<<" st.y="<<st.y<<" st.p_x="<<st.p_x<<" st.p_y="<<st.p_y<<endl;
 90     //----------------------------------------
 91     queue<point> q;
 92     while(!q.empty())
 93         q.pop();
 94     q.push(st);
 95     memset(vis,0,sizeof(vis));
 96     while(!q.empty())
 97     {
 98         point cur=q.front();q.pop();    
 99         //----------------------------------------
100     //        cout<<"cur.x="<<cur.x<<" cur.y="<<cur.y<<" cur.p_x="<<cur.p_x<<" cur.p_y="<<cur.p_y<<endl;
101     //    cout<<"-----------------------------\n";
102         //----------------------------------------
103         point next,pre;
104         if(map[cur.x][cur.y]==‘T‘)
105             return cur.ans;
106         for(int i=0;i<4;i++)
107         {
108             next=cur;
109             next.x=cur.x+dir[i][0];
110             next.y=cur.y+dir[i][1];
111             if(!isok(next.x,next.y))
112                 continue;
113             if(vis[next.x][next.y][i])
114                 continue;
115             pre=cur;
116             switch(i)
117             {
118                 case 0: pre.x=cur.x+1;break;
119                 case 1: pre.x=cur.x-1;break;
120                 case 2: pre.y=cur.y+1;break;
121                 case 3: pre.y=cur.y-1;break;
122             }
123             if(!bfs_person(pre,cur))//搜寻人是否能走到特定的位置
124                 continue;
125             vis[next.x][next.y][i]=1;
126             next.ans=cur.ans+tmp;
127             next.ans=next.ans+P[i];
128             next.p_x=cur.x;next.p_y=cur.y;
129             q.push(next);
130         }
131     }
132     return "Impossible.";
133 }
134 
135 int main()
136 {
137     int cas=1;
138     while(scanf("%d%d",&R,&C) && (R+C))
139     {
140         getchar();
141         for(int i=0;i<R;i++)
142             gets(map[i]);
143 
144         //---------------------------------------
145     //    for(int i=0;i<R;i++)
146         //    cout<<map[i]<<endl;
147         //----------------------------------------
148 
149         printf("Maze #%d\n",cas++);
150         //printf("%s\n",bfs_box());
151         cout<<bfs_box()<<endl<<endl;
152     }
153     return 0;
154 }