제출 #1208889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208889		HappyCapybara	Toy (CEOI24_toy)	C++20	100 / 100	192 ms	36652 KiB

Main

#include<bits/stdc++.h>
using namespace std;

int main(){
    int w, h, hl, vl, xh, y, x, yv;
    cin >> w >> h >> hl >> vl >> xh >> y >> x >> yv;
    vector<vector<bool>> g(h, vector<bool>(w, true));
    int tx, ty;
    for (int i=0; i<h; i++){
        string s;
        cin >> s;
        for (int j=0; j<w; j++){
            if (s[j] == 'X') g[i][j] = false;
            if (s[j] == '*'){
                tx = j;
                ty = i;
            }
        }
    }
    vector<vector<int>> l(h, vector<int>(w)), r(h, vector<int>(w)), u(h, vector<int>(w)), d(h, vector<int>(w));
    for (int i=0; i<h; i++){
        for (int j=0; j<w; j++){
            if (!g[i][j]){
                l[i][j] = -1;
                u[i][j] = -1;
                continue;
            }
            if (j == 0) l[i][j] = 0;
            else l[i][j] = l[i][j-1]+1;
            if (i == 0) u[i][j] = 0;
            else u[i][j] = u[i-1][j]+1;
        }
    }
    for (int i=h-1; i>=0; i--){
        for (int j=w-1; j>=0; j--){
            if (!g[i][j]){
                r[i][j] = -1;
                d[i][j] = -1;
                continue;
            }
            if (j == w-1) r[i][j] = 0;
            else r[i][j] = r[i][j+1]+1;
            if (i == h-1) d[i][j] = 0;
            else d[i][j] = d[i+1][j]+1;
        }
    }
    vector<vector<bool>> seen(h, vector<bool>(w, false));
    queue<pair<int,int>> q;
    q.push({y, x});
    while (!q.empty()){
        int y = q.front().first, x = q.front().second;
        q.pop();
        if (seen[y][x]) continue;
        seen[y][x] = true;
        if (y == ty && x == tx){
            cout << "YES" << endl;
            return 0;
        }
        int lm = x-l[y][x], rm = x+r[y][x], um = y-u[y][x], dm = y+d[y][x];
        if (y > 0){
            if (min(rm, x+r[y-1][x])-max(lm, x-l[y-1][x])+1 >= hl) q.push({y-1, x});
        }
        if (y < h-1){
            if (min(rm, x+r[y+1][x])-max(lm, x-l[y+1][x])+1 >= hl) q.push({y+1, x});
        }
        if (x > 0){
            if (min(dm, y+d[y][x-1])-max(um, y-u[y][x-1])+1 >= vl) q.push({y, x-1});
        }
        if (x < w-1){
            if (min(dm, y+d[y][x+1])-max(um, y-u[y][x+1])+1 >= vl) q.push({y, x+1});
        }
    }
    cout << "NO" << endl;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27