1 条题解
-
0赵青海 (huhe) LV 7 SU @ 2021-8-7 21:05:12
C++ :
#include <iostream> #include <cstdio> #include <queue> using namespace std; const int maxn = 5e2+7; 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}; //普通方向数组 //设0是立着,1是横着,2是竖着,这三种状态 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; //在dir数组里,0和1是左右,2和3是上下 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; }
- 1
信息
- ID
- 83
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 63
- 已通过
- 43
- 上传者