제출 #1345493

#제출 시각아이디문제언어결과실행 시간메모리
1345493vtnooMaze (JOI23_ho_t3)C++20
24 / 100
41 ms20504 KiB
#include <bits/stdc++.h>
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define pb push_back
using namespace std;
typedef long long ll;

const int N=3000,INF=1e9;
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};

vector<string>A;
int r,c,n;

void chmin(int &a,int b){
    a=min(a,b);
}

bool safe(int x,int y){
    return x>=0&&x<r&&y>=0&&y<c;
};

int anc[N][N];
queue<pair<int,int>>q,q1,q2;
vector<vector<int>>dist;
vector<vector<bool>>disp;

void bfs_reachable(){  
    vector<pair<int,int>>add;
    while(sz(q)){
        auto [i,j]=q.front();q.pop();
        L(k,0,3){
            int ni=i+di[k],nj=j+dj[k];
            if(safe(ni,nj)&&disp[ni][nj]){
                disp[ni][nj]=false;
                if(A[ni][nj]!='#'){
                    q.push({ni,nj});
                }else{
                    add.pb({ni,nj});
                    q1.push({ni,nj});
                }                
            }
        }
    }
    for(auto x:add){
        q.push(x);
    }
}

void bfs_extend(){
    while(sz(q1)){
        auto [i,j]=q1.front();q1.pop();
        L(k,1,n-1){
            int ni=i+k;
            if(safe(ni,j)&&disp[ni][j]){
                A[ni][j]='.';
                disp[ni][j]=false;
                q2.push({ni,j});
            }
            ni=i-k;
            if(safe(ni,j)&&disp[ni][j]){
                A[ni][j]='.';
                disp[ni][j]=false;
                q2.push({ni,j});
            }
        }
    }
    while(sz(q2)){
        auto [i,j]=q2.front();q2.pop();
        L(k,1,n-1){
            int nj=j+k;
            if(safe(i,nj)&&disp[i][nj]){
                A[i][nj]='.';
                disp[i][nj]=false;
                q.push({i,nj});
            }
            nj=j-k;
            if(safe(i,nj)&&disp[i][nj]){
                A[i][nj]='.';
                disp[i][nj]=false;
                q.push({i,nj});
            }
        }
    }
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    cin>>r>>c>>n;
    int sr,sc,gr,gc;cin>>sr>>sc>>gr>>gc;
    sr--,sc--,gr--,gc--;
    A.resize(r);
    dist.resize(r,vector<int>(c,INF));
    disp.resize(r,vector<bool>(c,INF));
    L(i,0,r-1){
        cin>>A[i];
    }
    int ans=0;
    disp[sr][sc]=false;
    q.push({sr,sc});
    bfs_reachable();
    while(1){
        if(!disp[gr][gc])break; 
        ans++;
        bfs_extend();
        bfs_reachable();
    }
    cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...