제출 #1342784

#제출 시각아이디문제언어결과실행 시간메모리
1342784vjudge1Toy (CEOI24_toy)C++20
9 / 100
416 ms13920 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];


ll w, h, k, l;
ll tx, ty;
ll p[1505][1505];
bool v[361][361][11][11];

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

bool ok(ll r1, ll c1, ll r2, ll c2) {
    if (r1 < 0 || r2 >= h || c1 < 0 || c2 >= w) return false;
    ll s = p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
    return s == 0;
}

bool Bfs(ll x1, ll y1, ll x2, ll y2) {
    queue<Cor> q;
    ll h0 = x2 - x1;
    ll v0 = y1 - y2;
    
    q.push({x1, y1, x2, y2});
    v[x1][y2][h0][v0] = true;

    ll dx[] = {1, -1, 0, 0};
    ll dy[] = {0, 0, 1, -1};

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

        if (tx >= c.x1 && tx < c.x1 + k && ty == c.y1 && ty >= c.y2 && ty < c.y2 + l && tx == c.x2) return true;

        for (ll i = 0; i < 4; ++i) {
            ll nx1 = c.x1 + dx[i];
            ll ny1 = c.y1 + dy[i];
            if (ok(ny1, nx1, ny1, nx1 + k - 1)) {
                if (c.x2 >= nx1 && c.x2 < nx1 + k && ny1 >= c.y2 && ny1 < c.y2 + l) {
                    ll hf = c.x2 - nx1;
                    ll vf = ny1 - c.y2;
                    if (!v[nx1][c.y2][hf][vf]) {
                        v[nx1][c.y2][hf][vf] = true;
                        q.push({nx1, ny1, c.x2, c.y2});
                    }
                }
            }
        }

        for (ll i = 0; i < 4; ++i) {
            ll nx2 = c.x2 + dx[i];
            ll ny2 = c.y2 + dy[i];
            if (ok(ny2, nx2, ny2 + l - 1, nx2)) {
                if (nx2 >= c.x1 && nx2 < c.x1 + k && c.y1 >= ny2 && c.y1 < ny2 + l) {
                    ll hf = nx2 - c.x1;
                    ll vf = c.y1 - ny2;
                    if (!v[c.x1][ny2][hf][vf]) {
                        v[c.x1][ny2][hf][vf] = true;
                        q.push({c.x1, c.y1, nx2, ny2});
                    }
                }
            }
        }
    }
    return false;
}


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

    for (ll i = 0; i < h; ++i) {
        for (ll j = 0; j < w; ++j) {
            char c; cin >> c;
            p[i + 1][j + 1] = p[i][j + 1] + p[i + 1][j] - p[i][j] + (c == 'X');
            if (c == '*') { tx = j; ty = i; }
        }
    }

    if (Bfs(x1, y1, x2, y2)) 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...