제출 #1046147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046147		VahanAbraham	Toy (CEOI24_toy)	C++17	100 / 100	108 ms	42576 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>

using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen(".out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 1505;
const ll oo = 100000000000000000, MOD = 1000000007;

struct cord {
    int x, y;
};

char grid[N][N];
bool ok[N][N];
int lhor[N][N], rhor[N][N], lver[N][N], rver[N][N];
int w, h, k, l, xend, yend;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

queue<pair<int,int>> q;

pair<int, int> hatvumen(cord hor, cord ver) {
    int i = ver.x;
    if (hor.y >= ver.y && hor.y <= ver.y + l - 1 && i >= hor.x && i <= hor.x + k - 1) {
        return { hor.y,i};
    }
    return{ -1,-1 };
}

int hatacmas(int l1, int r1, int l2, int r2) {
    return min(r2, r1) - max(l1, l2) + 1;
}


void solve() {
    cin >> w >> h >> k >> l;
    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;
    ++xh;
    ++yh;
    ++xv;
    ++yv;
    cord hor, ver;
    hor.x = xh;
    hor.y = yh;
    ver.x = xv;
    ver.y = yv;
    q.push(hatvumen(hor, ver));
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == '*') {
                xend = j, yend = i;
            }
        }
    }
    for (int i = 1; i <= h; ++i) {
        lhor[i][0] = 1;
        for (int j = 1; j <= w; ++j) {
            lhor[i][j] = lhor[i][j-1];
            if (grid[i][j - 1] == 'X') {
                lhor[i][j] = j;
            }
        }
    }
    for (int i = 1; i <= h; ++i) {
        rhor[i][w + 1] = w;
        for (int j = w; j >= 1; --j) {
            rhor[i][j] = rhor[i][j + 1];
            if (grid[i][j + 1] == 'X') {
                rhor[i][j] = j;
            }
        }
    }
    for (int j = 1; j <= w; ++j) {
        lver[0][j] = 1;
        for (int i = 1; i <= h; ++i) {
            lver[i][j] = lver[i-1][j];
            if (grid[i-1][j] == 'X') {
                lver[i][j] = i;
            }
        }
    }
    for (int j = 1; j <= w; ++j) {
        rver[h + 1][j] = h;
        for (int i = h; i >= 1; --i) {
            rver[i][j] = rver[i+1][j];
            if (grid[i+1][j] == 'X') {
                rver[i][j] = i;
            }
        }
    }
    ok[hatvumen(hor, ver).fr][hatvumen(hor, ver).sc] = 1;
    while (q.empty() != 1) {
        pair<int, int> p = q.front();
        //cout << p.fr << " " << p.sc << endl;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int x1 = p.fr + dx[i];
            int y1 = p.sc + dy[i];
            if (grid[x1][y1] != 'X' && ok[x1][y1]!=1 && x1>=1 &&x1<=h && y1>=1 && y1<=w ) {
                if (hatacmas(lhor[x1][y1],rhor[x1][y1],lhor[p.fr][p.sc],rhor[p.fr][p.sc]) >= k && hatacmas(lver[x1][y1], rver[x1][y1], lver[p.fr][p.sc], rver[p.fr][p.sc]) >=l) {
                    ok[x1][y1] = 1;
                    q.push({ x1,y1 });
                }
            }
        }
    }
    if (ok[yend][xend] == 1) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

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