Submission #1040093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040093		TAhmed33	Maze (JOI23_ho_t3)	C++98	100 / 100	350 ms	68564 KiB

Main

    #include<bits/stdc++.h>
    using namespace std;
    const int dx[4] = {-1, +1, 0, 0};
    const int dy[4] = {0, 0, -1, +1};
    int main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, m, k, r1, c1, r2, c2;
        cin >> n >> m >> k >> r1 >> c1 >> r2 >> c2;
        --r1, --c1, --r2, --c2;
        vector<vector<int>> d(n, vector<int>(m, -1));
        vector<vector<char>> a(n, vector<char>(m));
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                cin >> a[i][j];
            }
        }
        queue<pair<int, int>> q1;
        queue<tuple<int, int, int, int>> q2;
        q1.push({r1, c1});
        d[r1][c1] = 0;
        auto inside = [&](int x, int y){
            return -1 < x && x < n && -1 < y && y < m;
        };
        while(!q1.empty() || !q2.empty()){
            while(!q1.empty()){
                int x, y;
                tie(x, y) = q1.front(); q1.pop();
                for(int i = 0; i < 4; ++i){
                    int new_x = x + dx[i];
                    int new_y = y + dy[i];
                    if(inside(new_x, new_y) && d[new_x][new_y] == -1){
                        if(a[new_x][new_y] == '.'){
                            d[new_x][new_y] = d[x][y];
                            q1.push({new_x, new_y});
                        }
                        else{
                            d[new_x][new_y] = d[x][y] + 1;
                            q2.push({new_x, new_y, k - 1, k - 1});
                        }
                    }
                }
            }
            while(!q2.empty()){
                int x, y, sx, sy;
                tie(x, y, sx, sy) = q2.front(); q2.pop();
     
                if(sx == 0 || sy == 0){
                    q1.push({x, y});
                }
                for(int i = 0; i < 4; ++i){
                    int new_x = x + dx[i];
                    int new_y = y + dy[i];
                    int new_sx = sx - abs(dx[i]);
                    int new_sy = sy - abs(dy[i]);
                    if(inside(new_x, new_y) && d[new_x][new_y] == -1 && new_sx >= 0 && new_sy >= 0){
                        d[new_x][new_y] = d[x][y];
                        q2.push({new_x, new_y, new_sx, new_sy});
                    }
                }
            }
        }
        cout << d[r2][c2] << '\n';
        return 0;
    }

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6