제출 #1354484

#제출 시각아이디문제언어결과실행 시간메모리
1354484nathlol2Toy (CEOI24_toy)C++20
0 / 100
4 ms1604 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 95;
int n, m, k, l, xh, yh, xv, yv, ex, ey, okh[N][N], okv[N][N], vis[N][N][10][10], dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
string tb[N];
queue<tuple<int, int, 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({xv, yh, xv - xh, yh - yv});
    vis[xv][yh][xv - xh][yh - yv] = 1;
    while(!q.empty()){
        auto [x, y, ox, oy] = q.front();
        q.pop();
        int rx = x - ox, ry = y - oy;
        //move h
        for(int i = 0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i], tox = ox - dx[i], toy = oy + dy[i];
            if(dx[i] == 0){
                if(okh[rx][ny] && 0 <= toy && toy < l && !vis[nx][ny][tox][toy]){
                    vis[nx][ny][tox][toy] = 1;
                    q.push({nx, ny, tox, toy});
                }
            }else{
                if(okh[rx + dx[i]][y] && 0 <= tox && tox < k && !vis[x][y][tox][toy]){
                    vis[x][y][tox][toy] = 1;
                    q.push({x, y, tox, toy});
                }
            }
        }
        //move v
        for(int i = 0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i], tox = ox + dx[i], toy = oy - dy[i];
            if(dy[i] == 0){
                if(okv[nx][ry] && 0 <= tox && tox < k && !vis[nx][ny][tox][toy]){
                    vis[nx][ny][tox][toy] = 1;
                    q.push({nx, ny, tox, toy});
                }
            }else{
                if(okv[x][ry + dy[i]] && 0 <= toy && toy < l && !vis[x][y][tox][toy]){
                    vis[x][y][tox][toy] = 1;
                    q.push({x, y, tox, toy});
                }
            }
        }
    }
    bool f = 0;
    for(int i = 0;i<k;i++) for(int j = 0;j<l;j++) f |= vis[ex][ey][i][j];
    cout << (f ? "YES" : "NO");
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…