Submission #1361908

#TimeUsernameProblemLanguageResultExecution timeMemory
1361908mariaclaraToy (CEOI24_toy)C++20
100 / 100
75 ms47356 KiB
#include<bits/stdc++.h> 

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MX = 1500;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back
#define fr first 
#define sc second

int N, M, A, B;
int sx, sy, fx, fy;
int u[MX][MX], l[MX][MX], r[MX][MX], d[MX][MX];
string v[MX];

string solve() {
    vector<vi> vis(N, vi(M));
    queue<pii> bfs;
    bfs.push({sx, sy});
    vis[sx][sy] = 1;

    while(!bfs.empty()) {
        auto [x, y] = bfs.front();
        bfs.pop();

        if(x == fx and y == fy) return "YES\n";

        // vizinhos
        for(int i = -1; i <= 1; i += 2) {
            if(0 <= x+i and x+i < N and !vis[x+i][y]) {
                int a = max(l[x+i][y], l[x][y]);
                int b = min(r[x+i][y], r[x][y]);
                if(b-a-1 >= B) bfs.push({x+i, y}), vis[x+i][y] = 1;
            }
            if(0 <= y+i and y+i < M and !vis[x][y+i]) {
                int a = max(u[x][y], u[x][y+i]);
                int b = min(d[x][y], d[x][y+i]);
                if(b-a-1 >= A) bfs.push({x, y+i}), vis[x][y+i] = 1;
            }
        }
    }
    
    return "NO\n";
}

int main() {

    cin >> M >> N >> B >> A;
    cin >> fx >> sx >> sy >> fx;

    for(int i = 0; i < N; i++) {
        cin >> v[i];
  
        for(int j = 0; j < M; j++) 
            if(v[i][j] == '*') fx = i, fy = j;
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(i == 0) u[i][j] = -1;
            else u[i][j] = u[i-1][j];

            if(j == 0) l[i][j] = -1;
            else l[i][j] = l[i][j-1];

            if(v[i][j] == 'X') u[i][j] = i, l[i][j] = j;
        }
    }
    
    for(int i = N-1; i >= 0; i--) {
        for(int j = M-1; j >= 0; j--) {
            if(i == N-1) d[i][j] = N;
            else d[i][j] = d[i+1][j];

            if(j == M-1) r[i][j] = M;
            else r[i][j] = r[i][j+1];

            if(v[i][j] == 'X') d[i][j] = i, r[i][j] = j;
        }
    }

    cout << solve();
}
#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...