제출 #1342701

#제출 시각아이디문제언어결과실행 시간메모리
1342701mrcat2011Toy (CEOI24_toy)C++20
35 / 100
958 ms36696 KiB
//Mrcat template

#include <bits/stdc++.h>
//#include <bits/extc++.h>

using namespace std;
//using namespace __gnu_pbds;

typedef int64_t ll;
typedef string str;
typedef double dbl;
typedef char boolean;   
//typedef size_t sz;

#define MOD 1000000000
#define println(n) cout << n << endl
#define print(n) cout << n << ' '
#define input(n) cin >> n;
#define vll vector<ll> 
#define vc vector<char>
#define vstr vector<str>
#define vdbl vector<dbl>
#define vbln vector<boolean>
#define vpll vector<pair<ll, ll>>
#define vplb vector<pair<ll, boolean>>  
#define vvl  vector<vector<ll>>
//#define sum(v) accumulate(all(v), 0LL) 
#define all(a) a.begin(), a.end()
#define mll map<ll, ll>
#define mcl map<char, ll>
#define mlb map<ll, boolean>
#define mcb map<char, bool>
#define mstrl map<str, ll>
#define mlstr map<ll, str>
#define sll set<ll> 
#define sc set<char>
#define sstr set<str>
#define sdbl set<dbl>
#define sbln set<boolean>
#define msll multiset<ll> 
#define msc multiset<char>
#define msstr multiset<str>
#define msdbl multiset<dbl>
#define msbln multiset<boolean>
#define pll pair<ll, ll>
//#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define hurryupmrcat ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

template<typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (T& x : v) is >> x;
    return is;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    for (T x : v) os << x << ' ';
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T>& st) {
    for (T x : st) os << x << ' ';
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, multiset<T>& mst) {
    for (T x : mst) os << x << ' ';
    return os;
}

vll stov(str s) {
    vll v;
    for (char c : s) {
        v.emplace_back(c - '0');
    }
    return v;
}


const ll MAX = 2e5 + 5;

struct BIT {
    ll n;
    vll ft;

    BIT(ll N) {
        n = N + 10;
        ft.assign(n + 5, 0);
    }

    void add(ll idx, ll val) {
        for (idx; idx <= n; idx += (idx & (-idx))) {
            ft[idx] += val;
        }
    }

    ll get(ll idx) {
        ll ret = 0;
        
        for (idx; idx >= 0; idx -= (idx & (-idx))) {
            ret += ft[idx];
        }

        return ret;
    }
};

bool Comp(pll p1, pll p2) {
    if (p1.second < p2.second) return false;
    return true;
}

const ll MAX_SZ = 2e5 + 10;
ll suf[MAX_SZ];


struct Cor {
    ll x1, y1, x2, y2;
};

ll w, h, k, l;
char g[100][100];
bool used[100][100][100][100];

ll cor_x[] = {0, 0, 1, -1};
ll cor_y[] = {1, -1, 0, 0};

bool Bfs(ll x1, ll y1, ll x2, ll y2, ll tx, ll ty) {
    queue<Cor> q;
    q.push({x1, y1, x2, y2});
    used[x1][y1][x2][y2] = true;

    while (!q.empty()) {
        Cor cur = q.front();
        q.pop();

        if (cur.x2 == tx && cur.y1 == ty) {
            return true;
        }

        for (ll i = 0; i < 4; ++i) {
            ll nx = cur.x1 + cor_x[i];
            ll ny = cur.y1 + cor_y[i];

            if (nx >= 0 && nx + k <= w && ny >= 0 && ny < h) {
                bool ok = true;
                for (ll j = 0; j < k; ++j) {
                    if (g[ny][nx + j] == 'X') {
                        ok = false; break;
                    }
                }

                if (ok && cur.x2 >= nx && cur.x2 < nx + k && ny >= cur.y2 && ny < cur.y2 + l) {
                    if (!used[nx][ny][cur.x2][cur.y2]) {
                        used[nx][ny][cur.x2][cur.y2] = true;
                        q.push({nx, ny, cur.x2, cur.y2});
                    }
                }
            }
        }

        for (ll i = 0; i < 4; ++i) {
            ll nx = cur.x2 + cor_x[i];
            ll ny = cur.y2 + cor_y[i];

            if (nx >= 0 && nx < w && ny >= 0 && ny + l <= h) {
                bool ok = true;
                for (ll j = 0; j < l; ++j) {
                    if (g[ny + j][nx] == 'X') {
                        ok = false; break;
                    }
                }
                if (ok && nx >= cur.x1 && nx < cur.x1 + k && cur.y1 >= ny && cur.y1 < ny + l) {
                    if (!used[cur.x1][cur.y1][nx][ny]) {
                        used[cur.x1][cur.y1][nx][ny] = true;
                        q.push({cur.x1, cur.y1, nx, ny});
                    }
                }
            }
        }
    }
    return false;
}

void solve() {
    cin >> w >> h >> k >> l;
    ll x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    ll tx, ty;
    for (ll i = 0; i < h; ++i) {
        for (ll j = 0; j < w; ++j) {
            cin >> g[i][j];
            if (g[i][j] == '*') {
                tx = j; ty = i;
            }
        }
    }

    if (Bfs(x1, y1, x2, y2, tx, ty)) {
        cout << "YES"<< endl;
    } else {
        cout << "NO"<< endl;
    }
}


int main(int argc, char const *argv[]) {  
    hurryupmrcat
    ll t = 1;
    //cin >> t;
   
    for (size_t cs = 1; cs <= t; ++cs) {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...