Submission #916333

#	Time	Username	Problem	Language	Result	Execution time	Memory
916333		berr	Maze (JOI23_ho_t3)	C++17	100 / 100	1445 ms	330832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1e9+7;
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int r, c, n; cin >> c>> r >> n;
 
    array<int, 2> s, g;
 
    cin >> s[0] >> s[1];
    cin >> g[0] >> g[1];
    

    s[0]--; s[1]--;
    g[0]--; g[1]--;
    
    vector a(c, vector(r, '0')); 

    for(int i=0; i<c; i++){
        for(int l=0; l<r; l++){
            cin >> a[i][l];
        }
    }

    int ans = 0;
    queue<array<int, 2>> q[2];
    int pos = 0;
 
    q[0].push(s);
 
    queue<array<int, 3>> sinir;
    queue<array<int, 3>>sinir2;
    vector<array<int, 3>> pf;

    int of = 500;
    auto check =[&](int x, int y, int z){
        if(x<0 || y<0) return 1;
        if(x>=c || y>=r) return 1;
        if(a[x][y]=='.'){
            q[z%2].push({x, y});
            return 1;
        }
        return 0;
    
    };
 
    vector vis(c, vector(r, 0));
    vector vis2(c, vector(r, 0));
    vector vis3(c, vector(r, 0));
    vector vis4(c, vector(r, 0));

    int anss = -1;
    while(pos <r*c && anss==-1){   
        if(q[pos%2].size()==0 ){
            pos++;

            while(sinir.size()){

                auto [z, x, y] = sinir.front();
                vis[x][y] = 0;
                if(z!=0)
                sinir2.push({n, x, y});
                else
                    pf.push_back({n-1, x, y});

                q[pos%2].push({x, y});
                sinir.pop();    
                //cout<<x<<" "<<y<<" "<<pos<<"\n";
                if(z<=0) continue;

                if(y-1>=0&&!vis[x][y-1] && !vis2[x][y-1]){
                    a[x][y-1] = '.';
                    vis2[x][y-1] = 1;
                    sinir.push({z-1, x, y-1});
                }
                
                if(y+1<r&&!vis[x][y+1] && !vis2[x][y+1]){
                    a[x][y+1] = '.';
                    vis2[x][y+1] = 1;
                    sinir.push({z-1, x, y+1});
                }
            }

            while(pf.size()){
                sinir2.push(pf.back());
                pf.pop_back();
            }
            //cout<<"\n";
            while(sinir2.size()){
                auto [z, x, y] = sinir2.front();
                vis[x][y] = 0;
                sinir2.pop();
               // cout<<z<<" "<<x<<" "<<y<<"\n";

                if(z<=0) continue;
                if(x-1>=0&&!vis[x-1][y] && !vis2[x-1][y]){
                    a[x-1][y] = '.';
                    vis2[x-1][y] = 1;
                    sinir2.push({z-1, x-1, y});
                }
                
                if(x+1<c&&!vis[x+1][y] && !vis2[x+1][y]){
                    a[x+1][y] = '.';
                    vis2[x+1][y] = 1;
                    sinir2.push({z-1, x+1, y});
                }
            }
 
            
        }
        else{
 
            while(q[pos%2].size()){
                auto [x, y] = q[pos%2].front();
                q[pos%2].pop();
                int ans = 0;
                if(vis[x][y]) continue;
 
                vis[x][y] = 1;
                if(x==g[0] && y == g[1]&& anss==-1){
                    anss = pos;
                } 
 
                ans += check(x-1, y, pos);
                ans += check(x+1, y, pos);
                ans += check(x, y-1, pos);
                ans += check(x, y+1, pos);
                if(ans!=4){
                    sinir.push({n, x, y});
                }
            }
        }
 
 
    }
 
    cout << anss <<"\n";
 
}   

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:9: warning: unused variable 'ans' [-Wunused-variable]
   29 |     int ans = 0;
      |         ^~~
Main.cpp:39:9: warning: unused variable 'of' [-Wunused-variable]
   39 |     int of = 500;
      |         ^~

• 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