Submission #1290047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290047		loom	Toy (CEOI24_toy)	C++20	100 / 100	284 ms	267044 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

const int N = 1505;
char a[N][N];
int lk[N][N], rk[N][N], ul[N][N], dl[N][N], vis[N][N];
int n, m, k, l, tx, ty;

bool dfs(int x, int y){
   vis[x][y] = 1;
   if(x == tx and y == ty) return 1;

   if(x > 1 and !vis[x-1][y] and min(rk[x-1][y], rk[x][y]) - max(lk[x-1][y], lk[x][y]) - 1 >= k and dfs(x-1, y)) return 1;
   if(x < n and !vis[x+1][y] and min(rk[x+1][y], rk[x][y]) - max(lk[x+1][y], lk[x][y]) - 1 >= k and dfs(x+1, y)) return 1;
   if(y > 1 and !vis[x][y-1] and min(dl[x][y-1], dl[x][y]) - max(ul[x][y-1], ul[x][y]) - 1 >= l and dfs(x, y-1)) return 1;
   if(y < m and !vis[x][y+1] and min(dl[x][y+1], dl[x][y]) - max(ul[x][y+1], ul[x][y]) - 1 >= l and dfs(x, y+1)) return 1;

   return 0;
}  

void solve(){
   int yk, xk, yl, xl;
   cin>>m>>n>>k>>l>>yk>>xk>>yl>>xl;
   xk++, yk++, xl++, yl++;

   for(int i = 1; i <= n; i++){
      lk[i][0] = 0;
      rk[i][m+1] = m+1;

      for(int j = 1; j <= m; j++){
         cin>>a[i][j];

         if(a[i][j] == '*'){
            tx = i;
            ty = j;
         }

         lk[i][j] = (a[i][j] == 'X' ? j : lk[i][j-1]);
      }

      for(int j = m; j > 0; j--) rk[i][j] = (a[i][j] == 'X' ? j : rk[i][j+1]);
   }

   for(int j = 1; j <= m; j++){
      ul[0][j] = 0;
      dl[n+1][j] = n+1;

      for(int i = 1; i <= n; i++) ul[i][j] = (a[i][j] == 'X' ? i : ul[i-1][j]);
      for(int i = n; i > 0; i--) dl[i][j] = (a[i][j] == 'X' ? i : dl[i+1][j]);
   }

   cout<<(dfs(xk, yl) ? "YES" : "NO");
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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