Submission #1364926

#TimeUsernameProblemLanguageResultExecution timeMemory
1364926talyToy (CEOI24_toy)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define all(x) (x).begin(),(n).end()


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k, l; cin >> n >> m >> k >> l;
    vector<vector<char> > mat(n, vector<char>(m));
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

    int qx=0, qy=0;
    vector<vector<int> > num_ver, num_hor, pas_ver, pas_hor;
    num_ver.resize(n, vector<int>(m));
    num_hor.resize(n, vector<int>(m));
    pas_ver.resize(n, vector<int>(m));
    pas_hor.resize(n, vector<int>(m));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> mat[i][j];
            if(mat[i][j]=='X'){
                num_ver[i][j]=0;
                num_hor[i][j]=0;
            }else if(mat[i][j]=='*'){
                qx=i;
                qy=j;
            }
            else{
                if(i==0){
                    num_ver[i][j]=1;
                }else{
                    num_ver[i][j]=num_ver[i-1][j]+1;
                }
                if(j==0){
                    num_hor[i][j]=1;
                }else{
                    num_hor[i][j]=num_hor[i][j-1]+1;
                }
            }
        }
    }
    for(int i=n-1; i>=0; i--){
        for(int j=m-1; j>=0; j--){
            if(mat[i][j]=='x'){
                num_ver[i][j]=0;
                num_hor[i][j]=0;
            }else{
                if(i!=n-1){
                    num_ver[i][j]=max(num_ver[i+1][j], num_ver[i][j]);
                }
                if(j!=m-1){
                    num_hor[i][j]=max(num_hor[i][j+1], num_hor[i][j]);
                }
            }
            if(num_ver[i][j]>=l)pas_ver[i][l]=1;
            if(num_hor[i][j]>=k)pas_hor[i][l]=1;
        }
    }
    vector<vector<int> > marc(n, vector<int>(m));
    queue<pii> pos;
    //vector<pii> viz = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    //pos.push({x1, y2});
    marc[x1][y2]=1;
    //while(!pos.empty()){
    //    int x=pos.front().first;
    //    int y=pos.front().second;
    //    pos.pop();
    //    for(pii p:viz){
    //        int ax=p.first;
    //        int ay=p.second;
    //        int nx=x+ax;
    //        int ny=y+ay;
    //        if(nx>=0&&ny>=0&&nx<n&&ny<m&&!marc[nx][ny]&&pas_ver[nx][ny]+pas_hor[nx][ny]==2){
    //            pos.push({nx, ny});
    //            marc[nx][ny]=1;
    //        }
    //    }
    //}
    if(marc[qx][qy]){
        cout << "YES"<<endl;
    }else{
        cout << "NO"<<endl;
    }


}
#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...