제출 #1365618

#제출 시각아이디문제언어결과실행 시간메모리
1365618talyToy (CEOI24_toy)C++20
100 / 100
195 ms337620 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define all(x) (x).begin(),(n).end()
vector<vector<int>> marc1;
// vector<vector<vector<vector<int>>>> marc;
int n, m, l, k;
vector<vector<char> > mat;
vector<vector<int>> dir, esq, cima, baixo;
vector<pii> viz = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

bool sol2(int x, int y){
    if(x<0||x>=n||y<0||y>=m)return 0;
    if(marc1[x][y])return 0;
    // cout << x << " "<<y<<endl;
    marc1[x][y]=1;
    if(dir[x][y]+esq[x][y]-1<k||cima[x][y]+baixo[x][y]-1<l)return 0;
    if(mat[x][y]=='*'){
        return 1;
    }
    // x, y-1
    if(y-1>=0&&min(cima[x][y], cima[x][y-1])+min(baixo[x][y], baixo[x][y-1])-1>=l&&sol2(x, y-1))return 1;
    if(y+1<m&&min(cima[x][y], cima[x][y+1])+min(baixo[x][y], baixo[x][y+1])-1>=l&&sol2(x, y+1))return 1;
    if(x+1<n&&min(esq[x][y], esq[x+1][y])+min(dir[x][y], dir[x+1][y])-1>=k&&sol2(x+1, y))return 1;
    if(x-1>=0&&min(esq[x][y], esq[x-1][y])+min(dir[x][y], dir[x-1][y])-1>=k&&sol2(x-1, y))return 1;
    return 0;
}

// bool sol(int x1, int y1, int x2, int y2){
//     // cout << x1 << " "<<y1<<" "<<x2<<" "<<y2<<endl;
//     if(x1<0||x1>=n||y1<0||y1>=m||x2<0||x2>=n||y2<0||y2>=m)return 0;
//     if(x1>=x2&&x1<=x2+l-1&&y2>=y1&&y2<=y1+k-1){
//         if(marc[x1][y1][x2][y2]!=0)return 0;
//         marc[x1][y1][x2][y2]=1;
//         for(int i=y1; i<=y1+k-1; i++){
//             if(i<0||i>=m||mat[x1][i]=='X')return 0;
//         }
//         for(int i=x2; i<=x2+l-1; i++){
//             if(i<0||i>=n||mat[i][y2]=='X')return 0;
//         }
//         if(mat[x1][y2]=='*')return 1;
//         for(auto [ax, ay]:viz){
//             if(sol(x1+ax, y1+ay, x2, y2))return 1;
//             if(sol(x1, y1, x2+ax, y2+ay))return 1;
//         }
//     }
//     return 0;
// }



signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> k >> l;
    // srand(time(0));
    // n=rand()%15+2;
    // m=rand()%15+2;
    // k=rand()%(n-1)+2;
    // l=rand()%(m-1)+2;
    swap(n, m);
    mat.resize(n, vector<char>(m));
    // marc.resize(n, vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(m, 0))));
    marc1.resize(n, vector<int>(m, 0));
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    // int x1=0, y1=0, x2=0, y2=0;
    swap(x1, y1);
    swap(x2, y2);
    dir.resize(n, vector<int>(m));
    esq.resize(n, vector<int>(m));
    cima.resize(n, vector<int>(m));
    baixo.resize(n, vector<int>(m));
    bool ok=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> mat[i][j];
            // int w=rand()%7;
            // if(!(i==0&&j<k)&&!(j==0&&i<l)){
            //     if(w>=2)mat[i][j]='.';
            //     else if(w==0)mat[i][j]='X';
            //     else{
            //         if(!ok){
            //             mat[i][j]='*';
            //             ok=1;
            //         }else{
            //             mat[i][j]='.';
            //         }
            //     }
            // }else{
            //     mat[i][j]='o';
            // }
            // cout << mat[i][j];
        }
        // cout << endl;
    }
    // if(!ok){
    //     mat[n-1][m-1]='*';
    // }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(mat[i][j]=='X'){
                esq[i][j]=0;
                cima[i][j]=0;
            }else{
                if(i==0) cima[i][j]=1;
                else cima[i][j]=cima[i-1][j]+1;
                if(j==0)esq[i][j]=1;
                else esq[i][j]=esq[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'){
                dir[i][j]=0;
                baixo[i][j]=0;
            }else{
                if(i==n-1)baixo[i][j]=1;
                else baixo[i][j]=baixo[i+1][j]+1;
                if(j==m-1)dir[i][j]=1;
                else dir[i][j]=dir[i][j+1]+1;
            }
        }
    }
    if(sol2(x1, y2)){
        cout << "YES"<<endl;
    }else cout << "NO"<<endl;
    // for(int i=0; i<n; i++){
    //     for(int j=0; j<m; j++){
    //         cout << marc1[i][j];
    //     }
    //     cout << endl;
    // }
    // if(sol(x1, y1, x2, y2)){
    //     cout << "YES"<<endl;
    // }else cout << "NO"<<endl;

}
// 8 6 2 3
// 0 0 0 0
// ...X..*.
// .......X
// ...X....
// ........
// ..X..X..
// ..X.....
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…