Submission #1184614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184614		cpp_noob	Maze (JOI23_ho_t3)	C++20	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int R,C,N,sx,sy,gx,gy;
const int inf = 1e9;

int check(int x,int y){
    return x>=0 and x<R and y>=0 and y<C;
}

int dx[4] = {1,-1, 0, 0};
int dy[4] = { 0, 0,1,-1};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin>>R>>C>>N>>sx>>sy>>gx>>gy;
    sx--; sy--; gx--; gy--;
    vector<vector<char>> graph(R,vector<char>(C));
    vector<vector<int>> cost(R,vector<int>(C,inf));
    vector<vector<bool>> vis(R,vector<bool>(C,false));

    for(int i = 0;i<R;i++){
        for(int j = 0;j<C;j++){
            cin>>graph[i][j];
        }
    }

    queue<pair<int,int>> Q;
    Q.push({sx,sy});
    cost[sx][sy] = 0;
    

    while(!Q.empty()){
        auto [x,y] = Q.front(); Q.pop();

        if(vis[x][y])continue;

        vis[x][y] = true;

        for(int i = 0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(check(nx,ny)==0)continue;
            
            if(graph[nx][ny] == '.'){
                
                    cost[nx][ny] = min(cost[nx][ny],cost[x][y]);
                    Q.push({nx,ny});
                
                
            }else{
                for(int j = nx-(N-1);j<=nx+(N-1);j++){
                    for(int k = ny;k<ny+N;k++){
                        if(check(j,k)==1){
                            cost[j][k] = min(cost[x][y]+1,cost[j][k]);
                            Q.push({j,k});
                        }
                    }
                }
            }

        }
        
    }
    cout<<cost[gx][gy];


    return 0;
}

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