1 条题解

  • 0
    @ 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
    难度
    2
    标签
    递交数
    59
    已通过
    39
    上传者