Submission #1163133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163133		adhityamv	Maze (JOI23_ho_t3)	C++20	0 / 100	2094 ms	43256 KiB

Main

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
const int INF=1000000000000000000;
//const int INF=1e9;
const int N=1000000;
const int M=7+1e9;
const int ln=20;
struct Mint{   
    int n;
    Mint(int nn){
        n=nn%M;
    }
    Mint(){
        n=0;
    }
    Mint& operator+=(Mint const& m){
        n=(n+m.n)%M;
        return *this;
    }
    Mint& operator*=(Mint const& m){
        n=(n*m.n)%M;
        return *this;
    }
    Mint& operator-=(Mint const& m){
        n=(n+M-m.n)%M;
        return *this;
    }
    friend Mint binpow(Mint a,int b){
        if(b==0) return Mint(1);
        Mint r=binpow(a,b/2LL);
        r*=r;
        if(b%2==0) return r;
        r*=a;
        return r;
    }
    friend Mint inverse(Mint a){
        return binpow(a,M-2);
    }
    Mint& operator/=(Mint const &b){
        return (*this)*=inverse(b);
    }
    friend Mint operator+(Mint a,Mint const b){
        return (a+=b);
    }
    friend Mint operator-(Mint a,Mint const b){
        return (a-=b);
    }
    friend Mint operator*(Mint a,Mint const b){
        return (a*=b);
    }
    friend Mint operator/(Mint a,Mint const b){
        return (a/=b);
    }
    friend Mint operator-(Mint a){
        return 0-a;
    }
    friend std::ostream& operator<<(std::ostream& os, Mint const& a){
        return os << a.n;
    }
    friend std::istream& operator>>(std::istream& is, Mint& a){
        return (is >> a.n);
    }
    friend bool operator==(Mint const& a,Mint const& b){
        return a.n==b.n;
    }
    friend bool operator!=(Mint const& a,Mint const& b){
        return a.n!=b.n;
    }
};
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
    return os << p.fi << "," << p.se << " ";
}
void solve(){
    int r,c,n;
    cin >> r >> c >> n;
    pair<int,int> s;
    cin >> s.fi >> s.se;
    pair<int,int> g;
    cin >> g.fi >> g.se;
    s.fi--,s.se--,g.fi--,g.se--;
    bool a[r][c];
    for(int i=0;i<r;i++){
        string s;
        cin >> s;
        for(int j=0;j<c;j++){
            if(s[j]=='.') a[i][j]=true;
            else a[i][j]=false;
        }
    }
    // there are two qs : 0 queue and 1 queue
    // once 0 queue is empty, all members of 1 queue are white, some of them are in 0 queue
    // continue till 1 queue and 0 queue empty
    int ans[r][c];
    ans[s.fi][s.se]=0;
    deque<pii> zero;
    deque<pii> one;
    int val=0;
    bool zvisit[r][c];
    bool ovisit[r][c];
    bool alrzer[r][c];
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            zvisit[i][j]=false;
            ovisit[i][j]=false;
            ans[i][j]=INF;
            alrzer[i][j]=false;
        }
    }
    zvisit[s.fi][s.se]=true;
    ovisit[s.fi][s.se]=true;
    for(int i=s.fi-n;i<=s.fi+n;i++){
        for(int j=s.se-n;j<=s.se+n;j++){
            if(0<=i && i<r && 0<=j && j<c){
                if(i==s.fi+n|| i==s.fi-n) if(j==s.se+n || j==s.se-n) continue;
                ans[i][j]=val+1;
                ovisit[i][j]=true;
                one.push_back(mp(i,j));
            }
        }
    }
    ans[s.fi][s.se]=0;
    if(s.fi!=0){
        if(a[s.fi-1][s.se]){
            zero.push_back(mp(s.fi-1,s.se));
            ans[s.fi-1][s.se]=val;
            alrzer[s.fi-1][s.se]=true;
        }
    }
    if(s.fi!=r-1){
        if(a[s.fi+1][s.se]){
            zero.push_back(mp(s.fi+1,s.se));
            ans[s.fi+1][s.se]=val;
            alrzer[s.fi+1][s.se]=true;
        }
    }
    if(s.se!=0){
        if(a[s.fi][s.se-1]){
            zero.push_back(mp(s.fi,s.se-1));
            ans[s.fi][s.se-1]=val;
            alrzer[s.fi][s.se-1]=true;
        }
    }
    if(s.se!=c-1){
        if(a[s.fi][s.se+1]){
            zero.push_back(mp(s.fi,s.se+1));
            ans[s.fi][s.se+1]=val;
            alrzer[s.fi][s.se+1]=true;
        }
    }
    if(zero.empty()){
        val++;
        while(!one.empty()){
            auto p=one.front();
            a[p.fi][p.se]=true;
            if(abs(p.fi-s.fi)+abs(p.se-s.se)==1){
                zero.push_back(p);
                alrzer[p.fi][p.se]=true;
            }
            one.pop_front();
        }
    }
    assert(!zero.empty());
    while(!zero.empty()){
        while(!zero.empty()){
            auto u=zero.front();
            zvisit[u.fi][u.se]=true;
            zero.pop_front();
            pii p=mp(-1,-1);
            if(u.fi!=0){
                auto np=mp(u.fi-1,u.se);
                if(zvisit[np.fi][np.se]) p=np;
                else if(a[np.fi][np.se] && !alrzer[np.fi][np.se]){
                    zero.push_back(mp(np.fi,np.se));
                    alrzer[np.fi][np.se]=true;
                    ans[np.fi][np.se]=val;
                }
            }
            if(u.fi!=r-1){
                auto np=mp(u.fi+1,u.se);
                if(zvisit[np.fi][np.se]) p=np;
                else if(a[np.fi][np.se] && !alrzer[np.fi][np.se]){
                    zero.push_back(mp(np.fi,np.se));
                    alrzer[np.fi][np.se]=true;
                    ans[np.fi][np.se]=val;
                }
            }
            if(u.se!=0){
                auto np=mp(u.fi,u.se-1);
                if(zvisit[np.fi][np.se]) p=np;
                else if(a[np.fi][np.se] && !alrzer[np.fi][np.se]){
                    zero.push_back(mp(np.fi,np.se));
                    alrzer[np.fi][np.se]=true;
                    ans[np.fi][np.se]=val;
                }
            }
            if(u.se!=c-1){
                auto np=mp(u.fi,u.se+1);
                if(zvisit[np.fi][np.se]) p=np;
                else if(a[np.fi][np.se] && !alrzer[np.fi][np.se]){
                    zero.push_back(mp(np.fi,np.se));
                    alrzer[np.fi][np.se]=true;
                    ans[np.fi][np.se]=val;
                }
            }
            assert(abs(p.fi-u.fi)+abs(p.se-u.se)==1);
            int li,ri,lj,rj;
            int exi,exj;
            if(u.fi==p.fi+1){
                li=ri=u.fi+n;
                exi=u.fi+n-1;
                exj=-1;
                lj=u.se-n;
                rj=u.se+n;
            }
            if(u.fi==p.fi-1){
                li=ri=u.fi-n;
                exi=u.fi-n+1;
                exj=-1;
                lj=u.se-n;
                rj=u.se+n;
            }
            if(u.se==p.se+1){
                lj=rj=u.se+n;
                exj=u.se+n-1;
                exi=-1;
                li=u.fi-n;
                ri=u.fi+n;
            }
            if(u.se==p.se-1){
                lj=rj=u.se-n;
                exj=u.se-n+1;
                exi=-1;
                li=u.fi-n;
                ri=u.fi+n;
            }
            for(int i=li;i<=ri;i++){
                for(int j=lj;j<=rj;j++){
                    if(0>i || i>=r || 0>j || j>=c) continue;
                    if(i==ri || i==li) if(j==rj || j==lj) continue;
                    if(!ovisit[i][j] && !zvisit[i][j]){
                        ans[i][j]=min(ans[i][j],val+1);
                        ovisit[i][j]=true;
                        one.push_back(mp(i,j));
                    }
                }
            }
            if(exj==-1){
                int i=exi;
                for(int j:{lj,rj}){
                    if(0>i || i>=r || 0>j || j>=c) continue;
                    if(i==ri || i==li) if(j==rj || j==lj) continue;
                    if(!ovisit[i][j] && !zvisit[i][j]){
                        ans[i][j]=val+1;
                        ovisit[i][j]=true;
                        one.push_back(mp(i,j));
                    }
                }
            }
            if(exi==-1){
                int j=exj;
                for(int i:{li,ri}){
                    if(0>i || i>=r || 0>j || j>=c) continue;
                    if(i==ri || i==li) if(j==rj || j==lj) continue;
                    if(!ovisit[i][j] && !zvisit[i][j]){
                        ans[i][j]=val+1;
                        ovisit[i][j]=true;
                        one.push_back(mp(i,j));
                    }
                }
            }
        }
        while(!one.empty()){
            auto p=one.front();
            a[p.fi][p.se]=true;
            bool ad=false;
            if(p.fi!=0 && !ad){
                auto np=mp(p.fi-1,p.se);
                if(zvisit[np.fi][np.se]){
                    ad=true;
                }
            }
            if(p.fi!=r-1 && !ad){
                auto np=mp(p.fi+1,p.se);
                if(zvisit[np.fi][np.se]){
                    ad=true;
                }
            }
            if(p.se!=0 && !ad){
                auto np=mp(p.fi,p.se-1);
                if(zvisit[np.fi][np.se]){
                    ad=true;
                }
            }
            if(p.se!=c-1 && !ad){
                auto np=mp(p.fi,p.se+1);
                if(zvisit[np.fi][np.se]){
                    ad=true;
                }
            }
            if(ad){
                zero.push_back(p);
                alrzer[p.fi][p.se]=true;
            }
            one.pop_front();
        }
        /*for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(ans[i][j]<=val && ans[i][j]!=-1){
                    if(mp(i,j)==s) cout << '?';
                    else cout << '.';
                } else cout << '#';
            }
            cout << "\n";
        }
        cout << "\n";
        cout << val << "\n";*/
        val++;
    }
    cout << ans[g.fi][g.se] << "\n";
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    //cin >> t;
    t=1;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

• 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