Submission #1364306

#TimeUsernameProblemLanguageResultExecution timeMemory
1364306AvianshToy (CEOI24_toy)C++20
100 / 100
287 ms496532 KiB
#include <bits/stdc++.h>

using namespace std;

int w,h,k,l;

void dfs(int x, int y, vector<vector<int>> &lef,vector<vector<int>> &rig,vector<vector<int>> &up,vector<vector<int>> &down, vector<vector<bool>> &vis){
    if(x<0||x>=h||y<0||y>=w){
        return;
    }
    vis[x][y]=1;
    //check up
    x--;
    if(x<0||x>=h||y<0||y>=w||vis[x][y]){
        //no good
    }
    else{
        //can go maybe maybe
        int l = max(lef[x][y],lef[x+1][y]);
        int r = min(rig[x][y],rig[x+1][y]);
        if(r-l-1>=k){
            //can go
            dfs(x,y,lef,rig,up,down,vis);
        }
    }
    x++;
    //check down
    x++;
    if(x<0||x>=h||y<0||y>=w||vis[x][y]){
        //no good
    }
    else{
        //can go maybe maybe
        int l = max(lef[x][y],lef[x-1][y]);
        int r = min(rig[x][y],rig[x-1][y]);
        if(r-l-1>=k){
            //can go
            dfs(x,y,lef,rig,up,down,vis);
        }
    }
    x--;
    //check right
    y++;
    if(x<0||x>=h||y<0||y>=w||vis[x][y]){
        //no good
    }
    else{
        //can go maybe maybe
        int u = max(up[x][y],up[x][y-1]);
        int d = min(down[x][y],down[x][y-1]);
        if(d-u-1>=l){
            //can go
            dfs(x,y,lef,rig,up,down,vis);
        }
    }
    y--;
    y--;
    if(x<0||x>=h||y<0||y>=w||vis[x][y]){
        //no good
    }
    else{
        //can go maybe maybe
        int u = max(up[x][y],up[x][y+1]);
        int d = min(down[x][y],down[x][y+1]);
        if(d-u-1>=l){
            //can go
            dfs(x,y,lef,rig,up,down,vis);
        }
    }
    y++;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> w >> h >> k >> l;
    int xh,yh,xv,yv;
    cin >> xh >> yh >> xv >> yv;
    int x,y;
    x=xv;
    y=yh;
    swap(x,y);
    //now x is row number and y is col number
    //start point
    string grid[h];
    for(int i = 0;i<h;i++){
        cin >> grid[i];
    }
    vector<vector<int>>lef(h,vector<int>(w));
    vector<vector<int>>rig(h,vector<int>(w));
    vector<vector<int>>up(h,vector<int>(w));
    vector<vector<int>>down(h,vector<int>(w));
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            lef[i][j]=-1;
            if(j){
                lef[i][j]=lef[i][j-1];
            }
            if(grid[i][j]=='X'){
                lef[i][j]=j;
            }
        }
        for(int j = w-1;j>=0;j--){
            rig[i][j]=w;
            if(j<w-1){
                rig[i][j]=rig[i][j+1];
            }
            if(grid[i][j]=='X'){
                rig[i][j]=j;
            }
        }
    }
    for(int j = 0;j<w;j++){
        for(int i = 0;i<h;i++){
            up[i][j]=-1;
            if(i){
                up[i][j]=up[i-1][j];
            }
            if(grid[i][j]=='X'){
                up[i][j]=i;
            }
        }
        for(int i = h-1;i>=0;i--){
            down[i][j]=h;
            if(i<h-1){
                down[i][j]=down[i+1][j];
            }
            if(grid[i][j]=='X'){
                down[i][j]=i;
            }
        }
    }
    vector<vector<bool>>vis(h,vector<bool>(w,0));
    dfs(x,y,lef,rig,up,down,vis);
    int tarx,tary;
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            if(grid[i][j]=='*'){
                tarx=i;
                tary=j;
            }
        }
    }
    if(vis[tarx][tary]){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...