Submission #916270

#	Time	Username	Problem	Language	Result	Execution time	Memory
916270		berr	Maze (JOI23_ho_t3)	C++17	35 / 100	93 ms	32356 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[max(r, c) / n +2];
    int pos = 0;

    q[0].push(s);

    queue<array<int, 2>> sinir;
    queue<array<int, 3>>sinir2;
    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].push({x, y});
            return 1;
        }
        return 0;
    
    };

   // c = column
    vector vis(c, vector(r, 0));
    vector vis2(c, vector(r, 0));
    vector vis3(c, vector(r, 0));
    int anss = -1;
    while(pos <max(r, c) / n +2 && anss==-1){   
        if(q[pos].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].push({x, y});
                sinir.pop();
                for(int i=1; i<=n; i++){
                    if(y-i<0) 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)});
                }
                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;
                }
                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;
                }
            }
        }
        else{
            while(q[pos].size()){
                auto [x, y] = q[pos].front();
                q[pos].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:35:9: warning: unused variable 'of' [-Wunused-variable]
   35 |     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