Submission #1368975

#TimeUsernameProblemLanguageResultExecution timeMemory
1368975888313666Toy (CEOI24_toy)C++20
9 / 100
7 ms10564 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> s;
v<v<int>> prer, prec, dp, lf, rt, up, dn;

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!=m) {
        //print(min(up[u][w], up[u+1][w])+min(dn[u][w], dn[u+1][w]));
        //print(b+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 (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!=n) {
        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
    s.resize(m);
    //print(n);
    for (int i=0; i<m; i++) cin>>s[i];
    //print(m);
    dp.assign(m+1, v<int>(n+1, 0));
    lf.assign(m+2, v<int>(n+2, -inf));
    up=rt=dn=lf;
    //print(m);
    for (int i=1; i<=m; i++) for (int j=1; j<=n; j++) if (s[i-1][j-1]!='X') {
        if (s[i-1][j-1]=='*') {
            x3=i, y3=j;
        }
        lf[i][j]=max(1, lf[i-1][j]+1);
        up[i][j]=max(1, up[i][j-1]+1);
    }
    //print(n);
    for (int i=m; i>0; --i) for (int j=n; j>0; --j) if (s[i-1][j-1]!='X') {
        rt[i][j]=max(1, rt[i+1][j]+1);
        dn[i][j]=max(1, dn[i][j+1]+1);
    }
    //print(a);
    dfs(yy1+1, x2+1);
    //cout<<x3 _ y3<<'\n';
    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...