题目链接：
源自Bloxorz游戏：
挺有意思的一题，搜索本身不难，主要在表示状态上想了很长时间。
木块的状态可以压缩为三种：直立，横放，竖放。每种状态记录最上边或者最右边的坐标即可。
初始状态不一定是竖直放的，我玩了几关游戏，初始状态都是竖直放的，我就默认为初始状态竖直了于是WA了几次……
也可能有这种情况：
7 5
######...##O..##...##.XX##...######还有最好把全部的图都读入进来之后再判断起始坐标，读一个点判一次容易出错。
单向广搜：
| 11520958 | Accepted | 10280K | 579MS | 5245B | 2013-04-25 12:02:20 |
View Code 1 #include2 #include 3 #include 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 else174 {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 | Accepted | 15176K | 844MS | 5944B | 2013-04-25 12:02:44 |
我想知道为什么跑得更慢了Orz……
View Code 1 #include2 #include 3 #include 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 else189 {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 }