Submission #916285

#	Time	Username	Problem	Language	Result	Execution time	Memory
916285		berr	Maze (JOI23_ho_t3)	C++17	35 / 100	116 ms	38156 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<string> a(c);
 
    for(auto &i: a){
        cin >> i;
    }
 
 
    int ans = 0;
    queue<array<int, 2>> q[2];
    int pos = 0;
 
    q[0].push(s);
 
    queue<array<int, 2>> sinir;
    queue<array<int, 3>>sinir2;
        queue<array<int, 3>>sinir3;
 
    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));
    int anss = -1;
    while(pos <r+c && anss==-1){   
        if(q[pos%2].size()==0 ){
            pos++;
            if(pos == (max(r, c)/n+2)) break;
            while(sinir.size()){
                auto [x, y] = sinir.front();
                vis[x][y] = 0;
                sinir2.push({x, y, 0});
                q[pos%2].push({x, y});
                sinir.pop();
                for(int i=1; i<=n; i++){
                    if(y-i<0) break;
                    if(vis[x][y-i]) 
                    if(vis2[x][y-i]) break;
                    a[x][y-i] = '.';
                    vis2[x][y-i] = 1;
                    sinir2.push({x, y-i, (i==n)});
                }
                for(int i=1; i<=n; i++){
                    if(y+i>=r) break;
                    if(vis[x][y+i]) break;
                   if(vis2[x][y+i]) break;
                    a[x][y+i] = '.';
                    vis2[x][y+i] = 1;
                    sinir2.push({x, y+i, (i==n)});
                }
 
            }
 
            while(sinir2.size()){
                auto [x, y, z] = sinir2.front();
                vis[x][y] = 0;
                sinir2.pop();
                for(int i=1; i<=n-z; i++){
                    if(x-i<0) break;
                    if(vis[x-i][y]) break;
                    if(vis3[x-i][y]) break;
                    a[x-i][y] = '.';
                    vis3[x-i][y] = 1;
                    sinir3.push({x-i, y, (i==n)});
 
                }
                for(int i=1; i<=n-z; i++){
                    if(x+i>=c) break;
                    if(vis[x+i][y]) break;
                    if(vis3[x+i][y]) break;
 
                    a[x+i][y] = '.';
                    vis3[x+i][y] = 1;
                    sinir3.push({x+i, y, (i==n)});
                }
            }
 
 
            
        }
        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({x, y});
                }
            }
        }
 
 
    }
 
    cout << anss;
 
}   

Compilation message (stderr)

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

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