2 条题解
-
1
#include<queue> #include<math.h> #include<stdio.h> #include<iostream> #include<vector> #include<iomanip> #include<string.h> #include<algorithm> #include<cmath> #include<cstdio> #include<utility> #include<cstring> #include<stack> #include<fstream> #include<string> using namespace std; typedef long long ll; const int N = 1e5 + 10; const int maxn = 5e2 + 10; const int INF = 0x3f3f3f3f; struct rec { int x , y , lie; }; int n , m; char Map[maxn][maxn]; int step[maxn][maxn][3]; int dir[4][2] = { 0 , -1 , 0 , 1 , -1 , 0 , 1 , 0 }; int next_x[3][4] = { { 0 , 0 , -2 , 1 } , { 0 , 0 , -1 , 1 } , { 0 , 0 , -1 , 2 } }; int next_y[3][4] = { { -2 , 1 , 0 , 0 } , { -1 , 2 , 0 , 0 } , { -1 , 1 , 0 , 0 } }; int next_lie[3][4] = { { 1, 1, 2 , 2 } , { 0 , 0 , 1 , 1 } , { 2 , 2 , 0 , 0 } }; struct rec st , ed; bool valid( int x , int y ) { if ( x <= 0 || x > n || y <= 0 || y > m ) { return false; } return true; } void parse_st_ed() { for ( int i = 1 ; i <= n ; i++ ) { for ( int j = 1 ; j <= m ; j++ ) { if ( Map[i][j] == 'O' ) { ed.x = i; ed.y = j; ed.lie = 0; Map[i][j] = '.'; } if ( Map[i][j] == 'X' ) { for ( int k = 0 ; k < 4 ; k++ ) { int dx = dir[k][0] + i; int dy = dir[k][1] + j; if ( valid( dx , dy ) && Map[dx][dy] == 'X' ) { st.x = min( dx , i ); st.y = min( dy , j ); st.lie = k < 2 ? 1 : 2; Map[i][j] = Map[dx][dy] = '.'; break; } } if ( Map[i][j] == 'X' ) { st.x = i; st.y = j; st.lie = 0; Map[i][j] = '.'; } } } } } bool check( rec next ) { if ( !valid( next.x , next.y ) ) { return false; } if ( Map[next.x][next.y] == '#' ) { return false; } if ( next.lie == 0 && Map[next.x][next.y] != '.' ) { return false; } if ( next.lie == 1 && Map[next.x][ next.y + 1 ] == '#' ) { return false; } if ( next.lie == 2 && Map[ next.x + 1 ][next.y] == '#' ) { return false; } return true; } int bfs() { for ( int i = 1 ; i <= n ; i++ ) { for ( int j = 1 ; j <= m ; j++ ) { for ( int k = 0 ; k < 3 ; k++ ) { step[i][j][k] = -1; } } } queue<rec> q; step[st.x][st.y][st.lie] = 0; q.push(st); while ( !q.empty() ) { rec now = q.front(); q.pop(); for ( int i = 0 ; i < 4 ; i++ ) { rec next; next.x = now.x + next_x[now.lie][i]; next.y = now.y + next_y[now.lie][i]; next.lie = next_lie[now.lie][i]; if ( check(next) && step[next.x][next.y][next.lie] == -1 ) { step[next.x][next.y][next.lie] = step[now.x][now.y][now.lie] + 1; q.push(next); if ( next.x == ed.x && next.y == ed.y && next.lie == ed.lie ) { return step[next.x][next.y][next.lie]; } } } } return -1; } int main() { while ( ~scanf( "%d %d" , &n , &m ) ) { if ( n == 0 && m == 0 ) { break; } for ( int i = 1 ; i <= n ; i++ ) { for ( int j = 1 ; j <= m ; j++ ) { cin >> Map[i][j]; } } parse_st_ed(); int ans = bfs(); if ( ans != -1 ) { printf( "%d\n" , ans ); } else { printf( "Impossible\n" ); } } return 0; }
信息
- ID
- 83
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 73
- 已通过
- 51
- 上传者