Submission #1069715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069715		vjudge1	Toy (CEOI24_toy)	C++17	0 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>
#define div /
#define ll long long

#define fore(i, l, r) for(int i=int(l); i<int(r); i++)
#define sz(a) int((a).size())

using namespace std;

const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1000000007;
const int MAX_N = 5e5+23;
const int N = 1e6;

int ansX,ansY,ans;
int w,h,k,l,xh,yh,xv,yv;
int visited[51][51][51][51];
char grid[1505][1505];
vector<pair<int,int>>monsters;

pair<int,int> overlap(int Xh, int Yh, int Xv, int Yv) {
    if(Yv >= Yh and Yv <= (Yh+k-1) and Xh >= Xv and Xh <= (Xv+l-1))
        return {Xh,Yv};
    return {-1,-1};
}

void rekurzija(int Xh, int Yh, int Xv, int Yv) {
    pair<int,int>check = overlap(Xh,Yh,Xv,Yv);
    if(check.first == -1 and check.second == -1)
        return;
    else if(check.first == ansX and check.second == ansY) {
        ans=1;
        return;
    } else if(visited[Xh][Yh][Xv][Yv])
        return;
    visited[Xh][Yh][Xv][Yv] = 1;
    fore(i,0,monsters.size()) {
        if(monsters[i].second == Yv and monsters[i].first >= Xv and monsters[i].first <= Xv+l-1) // dodiruje ga vertical linija
            return;
        if(monsters[i].first == Xh and monsters[i].second >= Yv and monsters[i].second <= Yv+k-1) // dodiruje ga horizontal linija
            return;
    }
    if(Xh > 0)
        rekurzija(Xh-1,Yh,Xv,Yv);
    if(Xh < h-1)
        rekurzija(Xh+1,Yh,Xv,Yv);
    if(Yh > 0)
        rekurzija(Xh,Yh-1,Xv,Yv);
    if(Yh < w-k)
        rekurzija(Xh,Yh+1,Xv,Yv);

    if(Xv > 0)
        rekurzija(Xh,Yh,Xv-1,Yv);
    if(Xv < h-l)
        rekurzija(Xh,Yh,Xv+1,Yv);
    if(Yv > 0)
        rekurzija(Xh,Yh,Xv,Yv-1);
    if(Yv < w-1)
        rekurzija(Xh,Yh,Xv,Yv+1);
}

void solve() {
    cin >> w >> h >> k >> l;
    cin >> xh >> yh >> xv >> yv;
    fore(i,0,h) {
        fore(j,0,w) {
            cin >> grid[i][j];
            if(grid[i][j] == '*') {
                ansX = i;
                ansY = j;
            } else if(grid[i][j] == 'X')
                monsters.push_back({i,j});
        }
    }
    rekurzija(yh,xh,yv,xv);
    if(ans)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);

    int t=1;
    while(t--) solve();
}

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