Submission #1225627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225627		TadijaSebez	Maze (JOI23_ho_t3)	C++20	100 / 100	585 ms	235248 KiB

Main

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

const int N=6000050;
const int inf=1e9+7;
char s[N];
int mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int main(){
    int n,m,k;
    scanf("%i %i %i",&n,&m,&k);
    int sx,sy;
    scanf("%i %i",&sx,&sy);
    int gx,gy;
    scanf("%i %i",&gx,&gy);
    vector<vector<int>> mat(n+1,vector<int>(m+1,inf));
    auto dist=mat;
    vector<vector<array<int,2>>> go(n+1,vector<array<int,2>>(m+1,{0,0}));
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            mat[i][j]=s[j]=='#';
        }
    }
    auto Valid=[&](int x,int y){
        return x>=1 && x<=n && y>=1 && y<=m;
    };
    queue<pair<int,int>> q[2];
    int now=0,pre=1;
    q[now].push({sx,sy});
    dist[sx][sy]=0;
    while(q[now].size()){
        for(int dir=0;dir<2;dir++){
            queue<pair<int,int>> all;
            while(q[now].size()){
                int x,y;tie(x,y)=q[now].front();
                q[now].pop();
                all.push({x,y});
                if(go[x][y][dir]>0){
                    for(int d=dir;d<4;d+=2){
                        int nx=x+mv[d][0];
                        int ny=y+mv[d][1];
                        if(Valid(nx,ny)&&dist[nx][ny]==inf){
                            dist[nx][ny]=dist[x][y];
                            q[now].push({nx,ny});
                            go[nx][ny]=go[x][y];
                            go[nx][ny][dir]--;
                        }
                    }
                }
            }
            q[now]=all;
        }
        while(q[now].size()){
            int x,y;tie(x,y)=q[now].front();
            q[now].pop();
            for(int d=0;d<4;d++){
                int nx=x+mv[d][0];
                int ny=y+mv[d][1];
                if(Valid(nx,ny)&&dist[nx][ny]==inf){
                    if(mat[nx][ny]){
                        dist[nx][ny]=dist[x][y]+1;
                        q[pre].push({nx,ny});
                        go[nx][ny]={k-1,k-1};
                    }else{
                        dist[nx][ny]=dist[x][y];
                        q[now].push({nx,ny});
                    }
                }
            }
        }
        swap(now,pre);
    }
    printf("%i\n",dist[gx][gy]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%i %i %i",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%i %i",&sx,&sy);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%i %i",&gx,&gy);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%s",s+1);
      |         ~~~~~^~~~~~~~~~

• 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