Submission #1354385

#TimeUsernameProblemLanguageResultExecution timeMemory
1354385nathlol2Toy (CEOI24_toy)C++20
0 / 100
7 ms9796 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 1505;
int n, m, k, l, xh, yh, xv, yv, ex, ey, okh[N][N], okv[N][N], ch[N][N], cv[N][N], ok[N][N], vis[N][N], dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
string tb[N];
queue<pair<int, int>> q;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> m >> n >> l >> k >> yv >> xv >> yh >> xh;
    ++xh, ++yh, ++xv, ++yv;
    for(int i = 1;i<=n;i++){
        cin >> tb[i];
        tb[i] = " " + tb[i];
        for(int j = 1;j<=m;j++){
            if(tb[i][j] == '*') ex = i, ey = j;
        }
    }
    for(int i = 1;i<=m;i++){
        int c = 0;
        for(int j = 1;j<=k;j++){
            if(tb[j][i] == 'X') ++c;
        }
        if(c == 0) okh[1][i] = 1;
        for(int j = 2;j + k - 1<=n;j++){
            if(tb[j - 1][i] == 'X') --c;
            if(tb[j + k - 1][i] == 'X') ++c;
            if(c == 0) okh[j][i] = 1;
        }
    }
    for(int i = 1;i<=n;i++){
        int c = 0;
        for(int j = 1;j<=l;j++){
            if(tb[i][j] == 'X') ++c;
        }
        if(c == 0) okv[i][1] = 1;
        for(int j = 2;j + l - 1<=m;j++){
            if(tb[i][j - 1] == 'X') --c;
            if(tb[i][j + l - 1] == 'X') ++c;
            if(c == 0) okv[i][j] = 1;
        }
    }
    q.push({xh, yh});
    ch[xh][yh] = 1;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        for(int i = 0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(okh[nx][ny] && !ch[nx][ny]){
                ch[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
    q.push({xv, yv});
    cv[xv][yv] = 1;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        for(int i = 0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(okv[nx][ny] && !cv[nx][ny]){
                cv[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
    for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) ok[i][j] = 1;
    for(int i = 1;i<=m;i++){
        int c = 0;
        for(int j = 1;j<=n;j++){
            if(ch[j][i]) ++c;
            if(j - k >= 1 && ch[j - k][i]) --c;
            ok[j][i] &= (c != 0); 
        }
    }
    for(int i = 1;i<=n;i++){
        int c = 0;
        for(int j = 1;j<=m;j++){
            if(cv[i][j]) ++c;
            if(j - l >= 1 && cv[i][j - l]) --c;
            ok[i][j] &= (c != 0);
        }
    }
    q.push({xv, yh});
    vis[xv][yh] = 1;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        for(int i = 0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(ok[nx][ny] && !vis[nx][ny]){
                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
    cout << (vis[ex][ey] ? "YES" : "NO");
}
#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...