Submission #1369027

#TimeUsernameProblemLanguageResultExecution timeMemory
1369027888313666Toy (CEOI24_toy)C++20
100 / 100
200 ms258396 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define v vector
#define _ <<' '<<
#define print(x) cout<<#x<<": "<<(x)<<endl
constexpr int inf=INT_MAX>>1;
int n,m, x1, yy1, x2, y2, x3, y3, a, b;
v<string> strrrrrr;
v<v<int>> prer, prec, dp, lf, rt, up, dn;

char s(const int i, const int j) {
    return strrrrrr[j-1][i-1];
}

void dfs(const int u, const int w) {
    //cout<<u _ w<<'\n';
    dp[u][w]=1;
    if (u!=1) {
        if (min(up[u][w], up[u-1][w])+min(dn[u][w], dn[u-1][w])>b && !dp[u-1][w]) {
            dfs(u-1, w);
        }
    }
    if (u!=n) {
        if (min(up[u][w], up[u+1][w])+min(dn[u][w], dn[u+1][w])>b && !dp[u+1][w]) {
            dfs(u+1, w);
        }
    }
    if (w!=1) {
        if (min(lf[u][w], lf[u][w-1])+min(rt[u][w], rt[u][w-1])>a && !dp[u][w-1]) {
            dfs(u, w-1);
        }
    }
    if (w!=m) {
        if (min(lf[u][w], lf[u][w+1])+min(rt[u][w], rt[u][w+1])>a && !dp[u][w+1]) {
            dfs(u, w+1);
        }
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>m>>a>>b>>x1>>yy1>>x2>>y2; // wtf who would use this coordinate system
    strrrrrr.resize(m);
    for (int i=0; i<m; i++) cin>>strrrrrr[i];
    dp.assign(n+1, v<int>(m+1, 0));
    lf.assign(n+2, v<int>(m+2, -inf));
    rt=dn=up=lf;
    dp[x1][y2]=1;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (s(i, j)!='X') {
        if (s(i, j)=='*') {
            x3=i, y3=j;
        }
        lf[i][j]=1+max(0, lf[i-1][j]);
        up[i][j]=1+max(0, up[i][j-1]);
        //cout<<i _ j _ up[i][j] _ "u\n";
    }
    for (int i=n; i>0; --i) for (int j=m; j>0; --j) if (s(i, j)!='X') {
        rt[i][j]=1+max(0, rt[i+1][j]);
        dn[i][j]=1+max(0, dn[i][j+1]);
        //cout<<i _ j _ dn[i][j] _ "d\n";
    }
    dfs(x2+1, yy1+1);
    if (dp[x3][y3]) cout<<"YES\n";
    else cout<<"NO\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...