Submission #1070028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070028		vjudge1	Toy (CEOI24_toy)	C++17	100 / 100	300 ms	295068 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 N = 1e6;

int w,h,k,l,xh,yh,xv,yv;
char grid[1505][1505];
int up[1505][1505],down[1505][1505],lijevo[1505][1505],desno[1505][1505],visited[1505][1505],ans;

void floodfill(int x, int y) {
    if(grid[x][y] == '*') {
        ans=1;
        return;
    }
    if(visited[x][y])
        return;
    visited[x][y] = 1;
    // pomjeranje u desno
    if(y < w-1)
        if(grid[x][y+1] != 'X' and min(up[x][y],up[x][y+1])+min(down[x][y],down[x][y+1])-1 >= l)
            floodfill(x,y+1);
    // pomjeranje u lijevo
    if(y > 0)
        if(grid[x][y-1] != 'X' and min(up[x][y],up[x][y-1])+min(down[x][y],down[x][y-1])-1 >= l)
            floodfill(x,y-1);

    // pomjeranje gore
    if(x > 0)
        if(grid[x-1][y] != 'X' and min(lijevo[x][y],lijevo[x-1][y])+min(desno[x][y],desno[x-1][y])-1 >= k)
            floodfill(x-1,y);
    // pomjeranje dole
    if(x < h-1)
        if(grid[x+1][y] != 'X' and min(lijevo[x][y],lijevo[x+1][y])+min(desno[x][y],desno[x+1][y])-1 >= k)
            floodfill(x+1,y);
}

void solve() {
    cin >> w >> h >> k >> l;
    cin >> xh >> yh >> xv >> yv;
    fore(i,0,h)
        fore(j,0,w)
            cin >> grid[i][j];
    fore(j,0,w) { // racunanje up i down
        fore(i,0,h) {
            if(grid[i][j] == 'X')
                up[i][j] = 0;
            else if(i==0)
                up[i][j] = 1;
            else if(i)
                up[i][j] = up[i-1][j]+1;
        }
        for(int i=h-1; i>=0; i--) {
            if(grid[i][j] == 'X')
                down[i][j] = 0;
            else if(i == h-1)
                down[i][j] = 1;
            else if(i < h-1)
                down[i][j] = down[i+1][j]+1;
        }
    }
    fore(i,0,h) { // racunanje left i desno
        fore(j,0,w) {
            if(grid[i][j] == 'X')
                desno[i][j] = 0;
            else if(j==0)
                desno[i][j] = 1;
            else if(j)
                desno[i][j] = desno[i][j-1]+1;
        }
        for(int j=w-1; j>=0; j--) {
            if(grid[i][j] == 'X')
                lijevo[i][j] = 0;
            else if(j == w-1)
                lijevo[i][j] = 1;
            else if(j < w-1)
                lijevo[i][j] = lijevo[i][j+1]+1;
        }
    }
    floodfill(yh,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: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27