POJ 3322 Bloxorz I

题目链接：http://poj.org/problem?id=3322

源自Bloxorz游戏：点此试玩

挺有意思的一题，搜索本身不难，主要在表示状态上想了很长时间。

木块的状态可以压缩为三种：直立，横放，竖放。每种状态记录最上边或者最右边的坐标即可。

初始状态不一定是竖直放的，我玩了几关游戏，初始状态都是竖直放的，我就默认为初始状态竖直了于是WA了几次……

也可能有这种情况：

7 5
#####
#...#
#O..#
#...#
#.XX#
#...#
#####

还有最好把全部的图都读入进来之后再判断起始坐标，读一个点判一次容易出错。

单向广搜：

11520958 gbr 3322 Accepted 10280K 579MS G++ 5245B 2013-04-25 12:02:20
View Code 
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 
  5 #define stand 0
  6 #define vert 1
  7 #define hori 2
  8 
  9 const int MAXN = 510;
 10 
 11 struct point
 12 {
 13     int step;
 14     int state;
 15     int x, y;
 16 };
 17 
 18 point move[3][4];
 19 
 20 char map[MAXN][MAXN];
 21 bool vis[MAXN][MAXN][4];
 22 int R, C;
 23 point st, ed;
 24 point Queue[ MAXN * MAXN * 4 + 10 ];
 25 
 26 //每个状态记录最上边或者最右边的一点坐标
 27 void init()
 28 {
 29     move[stand][0].x = -2;   //从站立向上倒
 30     move[stand][0].y = 0;
 31     move[stand][0].state = hori;
 32 
 33     move[stand][1].x = 1;   //从站立向下倒
 34     move[stand][1].y = 0;
 35     move[stand][1].state = hori;
 36 
 37     move[stand][2].x = 0;   //从站立向左倒
 38     move[stand][2].y = -1;
 39     move[stand][2].state = vert;
 40 
 41     move[stand][3].x = 0;  //从站立向右倒
 42     move[stand][3].y = 2;
 43     move[stand][3].state = vert;
 44 
 45     //======================
 46 
 47     move[vert][0].x = -1;   //从水平向上倒
 48     move[vert][0].y = 0;
 49     move[vert][0].state = vert;
 50 
 51     move[vert][1].x = 1;    //从水平向下倒
 52     move[vert][1].y = 0;
 53     move[vert][1].state = vert;
 54 
 55     move[vert][2].x = 0;    //从水平向左倒
 56     move[vert][2].y = -2;
 57     move[vert][2].state = stand;
 58 
 59     move[vert][3].x = 0;    //从水平向右倒
 60     move[vert][3].y = 1;
 61     move[vert][3].state = stand;
 62 
 63     //======================
 64 
 65     move[hori][0].x = -1;   //从竖直向上倒
 66     move[hori][0].y = 0;
 67     move[hori][0].state = stand;
 68 
 69     move[hori][1].x = 2;    //从竖直向下倒
 70     move[hori][1].y = 0;
 71     move[hori][1].state = stand;
 72 
 73     move[hori][2].x = 0;   //从竖直向左倒
 74     move[hori][2].y = -1;
 75     move[hori][2].state = hori;
 76 
 77     move[hori][3].x = 0;   //从竖直向右倒
 78     move[hori][3].y = 1;
 79     move[hori][3].state = hori;
 80     return;
 81 }
 82 
 83 bool check( int x, int y, int state )
 84 {
 85     if ( x >= 0 && x < R && y >= 0 && y < C && map[x][y] != '#' )
 86     {
 87         if ( state == stand && map[x][y] != 'E' ) return true;
 88         if ( state == vert && y - 1 >= 0 && map[x][y-1] != '#' ) return true;
 89         if ( state == hori && x + 1 < R && map[x+1][y] != '#' ) return true;
 90     }
 91     return false;
 92 }
 93 
 94 int BFS()
 95 {
 96     memset( vis, false, sizeof(vis) );
 97     vis[st.x][st.y][st.state] = true;
 98 
 99     int front = 0, rear = 0;
100 
101     Queue[ rear++ ] = st;
102 
103     while ( front < rear )
104     {
105         point cur = Queue[ front++ ];
106         if ( cur.x == ed.x && cur.y == ed.y && cur.state == ed.state )
107                 return cur.step;
108 
109         //printf("x=%d y=%d state=%d\n", cur.x, cur.y, cur.state);
110 
111         for ( int i = 0; i < 4; ++i )
112         {
113             int xx = cur.x + move[cur.state][i].x;
114             int yy = cur.y + move[cur.state][i].y;
115             int state = move[cur.state][i].state;
116             if ( !vis[xx][yy][state] && check( xx, yy, state ) )
117             {
118                     vis[xx][yy][state] = true;
119                     Queue[rear].x = xx;
120                     Queue[rear].y = yy;
121                     Queue[rear].state = state;
122                     Queue[rear].step = cur.step + 1;
123                     if ( Queue[rear].x == ed.x && Queue[rear].y == ed.y && Queue[rear].state == ed.state )
124                         return Queue[rear].step;
125                     ++rear;
126             }
127         }
128     }
129 
130     return -1;
131 }
132 
133 int main()
134 {
135     init();
136     //freopen( "s.out", "w", stdout );
137     while ( scanf( "%d%d", &R, &C ), R || C )
138     {
139         bool findst = false, finded = false;
140         for ( int i = 0; i < R; ++i )
141             scanf( "%s", map[i] );
142 
143         for ( int i = 0; (!finded || !findst) && i < R; ++i )
144         {
145             for ( int j = 0; (!finded || !findst) && j < C; ++j )
146             {
147                 if ( !findst && map[i][j] == 'X' )
148                 {
149                     if ( map[i - 1][j] == 'X' )
150                     {
151                         st.x = i - 1;
152                         st.y = j;
153                         st.state = hori;
154                     }
155                     else if ( map[i + 1][j] == 'X' )
156                     {
157                         st.x = i;
158                         st.y = j;
159                         st.state = hori;
160                     }
161                     else if ( map[i][j - 1] == 'X' )
162                     {
163                         st.x = i;
164                         st.y = j;
165                         st.state = vert;
166                     }
167                     else if ( map[i][j + 1] == 'X' )
168                     {
169                         st.x = i;
170                         st.y = j + 1;
171                         st.state = vert;
172                     }
173                     else
174                     {
175                         st.x = i;
176                         st.y = j;
177                         st.state = stand;
178                     }
179                     st.step = 0;
180                     findst = true;
181                 }
182                 if ( map[i][j] == 'O' )
183                 {
184                     ed.x = i;
185                     ed.y = j;
186                     ed.state = stand;
187                     finded = true;
188                 }
189             }
190         }
191         //printf("start: x=%d y=%d state=%d\n", st.x, st.y, st.state );
192         int ans = BFS();
193         if ( ans == -1 ) puts("Impossible");
194         else printf( "%d\n", ans );
195     }
196     return 0;
197 }

双向广搜：

11520960 gbr 3322 Accepted 15176K 844MS G++ 5944B 2013-04-25 12:02:44

我想知道为什么跑得更慢了Orz……

View Code 
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 
  5 #define stand 0
  6 #define vert 1
  7 #define hori 2
  8 
  9 const int MAXN = 510;
 10 
 11 struct point
 12 {
 13     int state;
 14     int x, y;
 15 };
 16 
 17 point move[3][4];
 18 
 19 char map[MAXN][MAXN];
 20 int vis[MAXN][MAXN][4];
 21 int step[MAXN][MAXN][4];
 22 int R, C;
 23 point st, ed;
 24 point Queue[ MAXN * MAXN * 4 + 10 ];
 25 
 26 //每个状态记录最上边或者最右边的一点坐标
 27 void init()
 28 {
 29     move[stand][0].x = -2;   //从站立向上倒
 30     move[stand][0].y = 0;
 31     move[stand][0].state = hori;
 32 
 33     move[stand][1].x = 1;   //从站立向下倒
 34     move[stand][1].y = 0;
 35     move[stand][1].state = hori;
 36 
 37     move[stand][2].x = 0;   //从站立向左倒
 38     move[stand][2].y = -1;
 39     move[stand][2].state = vert;
 40 
 41     move[stand][3].x = 0;  //从站立向右倒
 42     move[stand][3].y = 2;
 43     move[stand][3].state = vert;
 44 
 45     //======================
 46 
 47     move[vert][0].x = -1;   //从水平向上倒
 48     move[vert][0].y = 0;
 49     move[vert][0].state = vert;
 50 
 51     move[vert][1].x = 1;    //从水平向下倒
 52     move[vert][1].y = 0;
 53     move[vert][1].state = vert;
 54 
 55     move[vert][2].x = 0;    //从水平向左倒
 56     move[vert][2].y = -2;
 57     move[vert][2].state = stand;
 58 
 59     move[vert][3].x = 0;    //从水平向右倒
 60     move[vert][3].y = 1;
 61     move[vert][3].state = stand;
 62 
 63     //======================
 64 
 65     move[hori][0].x = -1;   //从竖直向上倒
 66     move[hori][0].y = 0;
 67     move[hori][0].state = stand;
 68 
 69     move[hori][1].x = 2;    //从竖直向下倒
 70     move[hori][1].y = 0;
 71     move[hori][1].state = stand;
 72 
 73     move[hori][2].x = 0;   //从竖直向左倒
 74     move[hori][2].y = -1;
 75     move[hori][2].state = hori;
 76 
 77     move[hori][3].x = 0;   //从竖直向右倒
 78     move[hori][3].y = 1;
 79     move[hori][3].state = hori;
 80     return;
 81 }
 82 
 83 bool check( int x, int y, int state )
 84 {
 85     if ( x >= 0 && x < R && y >= 0 && y < C && map[x][y] != '#' )
 86     {
 87         if ( state == stand && map[x][y] != 'E' ) return true;
 88         if ( state == vert && y - 1 >= 0 && map[x][y-1] != '#' ) return true;
 89         if ( state == hori && x + 1 < R && map[x+1][y] != '#' ) return true;
 90     }
 91     return false;
 92 }
 93 
 94 int BFS()
 95 {
 96     //memset( step, 0, sizeof(step) );
 97     memset( vis, 0, sizeof(vis) );
 98     vis[st.x][st.y][st.state] = 1;
 99     step[st.x][st.y][st.state] = 0;
100 
101     vis[ed.x][ed.y][ed.state] = 2;
102     step[ed.x][ed.y][ed.state] = 0;
103 
104     int front = 0, rear = 0;
105 
106     Queue[ rear++ ] = st;
107     Queue[ rear++ ] = ed;
108 
109     while ( front < rear )
110     {
111         point cur = Queue[ front++ ];
112 
113         for ( int i = 0; i < 4; ++i )
114         {
115             int xx = cur.x + move[cur.state][i].x;
116             int yy = cur.y + move[cur.state][i].y;
117             int state = move[cur.state][i].state;
118             if ( check( xx, yy, state ) )
119             {
120                 /*
121                 printf("pre:vis=%d st=%d x=%d y=%d %d\n", vis[cur.x][cur.y][cur.state],
122                     cur.state, cur.x, cur.y, step[cur.x][cur.y][cur.state] );
123                 printf("now:vis=%d st=%d x=%d y=%d %d\n\n", vis[cur.x][cur.y][cur.state],
124                     state, xx, yy, step[cur.x][cur.y][cur.state] + 1 );
125                 */
126                 if ( !vis[xx][yy][state] )
127                 {
128                     vis[xx][yy][state] = vis[cur.x][cur.y][cur.state];
129                     Queue[rear].x = xx;
130                     Queue[rear].y = yy;
131                     Queue[rear].state = state;
132                     step[xx][yy][state] = step[cur.x][cur.y][cur.state] + 1;
133                     ++rear;
134                 }
135                 else if ( vis[xx][yy][state] != vis[cur.x][cur.y][cur.state] )
136                 {
137                 //    printf("vis=%d x=%d y=%d st=%d\n", vis[xx][yy][state], xx, yy, state);
138                 //    printf("===%d %d===\n", step[xx][yy][state], step[cur.x][cur.y][cur.state] + 1 );
139                     return step[xx][yy][state] + step[cur.x][cur.y][cur.state] + 1;
140                 }
141             }
142         }
143     }
144 
145     return -1;
146 }
147 
148 int main()
149 {
150     init();
151     //freopen( "s.out", "w", stdout );
152     while ( scanf( "%d%d", &R, &C ), R || C )
153     {
154         bool findst = false, finded = false;
155         for ( int i = 0; i < R; ++i )
156             scanf( "%s", map[i] );
157 
158         for ( int i = 0; ( !finded || !findst ) && i < R; ++i )
159         {
160             for ( int j = 0; ( !finded || !findst ) && j < C; ++j )
161             {
162                 if ( !findst && map[i][j] == 'X' )
163                 {
164                     if ( map[i - 1][j] == 'X' )
165                     {
166                         st.x = i - 1;
167                         st.y = j;
168                         st.state = hori;
169                     }
170                     else if ( map[i + 1][j] == 'X' )
171                     {
172                         st.x = i;
173                         st.y = j;
174                         st.state = hori;
175                     }
176                     else if ( map[i][j - 1] == 'X' )
177                     {
178                         st.x = i;
179                         st.y = j;
180                         st.state = vert;
181                     }
182                     else if ( map[i][j + 1] == 'X' )
183                     {
184                         st.x = i;
185                         st.y = j + 1;
186                         st.state = vert;
187                     }
188                     else
189                     {
190                         st.x = i;
191                         st.y = j;
192                         st.state = stand;
193                     }
194                     findst = true;
195                 }
196                 if ( map[i][j] == 'O' )
197                 {
198                     ed.x = i;
199                     ed.y = j;
200                     ed.state = stand;
201                     finded = true;
202                 }
203             }
204         }
205         //printf("start: x=%d y=%d state=%d\n", st.x, st.y, st.state );
206         int ans = BFS();
207         if ( ans == -1 ) puts("Impossible");
208         else printf( "%d\n", ans );
209     }
210     return 0;
211 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/GBRgbr/p/3042187.html