Submission #1094371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094371		epicci23	Toy (CEOI24_toy)	C++17	100 / 100	193 ms	40804 KiB

Main

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;


void _(){

  int n,m,k,l,a,b,c,d;
  cin >> m >> n >> k >> l;
  cin >> b >> a >> d >> c;

  b++,a++,c++,d++;

  int t_a,t_b;

  vector<string> v;
  v.push_back(" ");

  for(int i=1;i<=n;i++){
  	string s;cin >> s;
  	s=" " + s;
  	for(int j=1;j<=m;j++){
  	  if(s[j]=='*'){
  	  	t_a=i;
  	  	t_b=j;
  	  }
  	}
  	v.push_back(s);
  }

  int lf[n+5][m+5],up[n+5][m+5],rg[n+5][m+5],dw[n+5][m+5];

  for(int i=1;i<=m;i++) dw[n+1][i]=n+1;
  for(int i=1;i<=n;i++) rg[i][m+1]=m+1;
  for(int i=1;i<=n;i++) lf[i][0]=0;
  for(int i=1;i<=m;i++) up[0][i]=0;

  for(int i=n;i>=1;i--){
  	for(int j=m;j>=1;j--){
      if(v[i][j]=='X'){
      	dw[i][j]=i;
      	rg[i][j]=j;
      }
      else{
      	dw[i][j]=dw[i+1][j];
      	rg[i][j]=rg[i][j+1];
      }
  	}
  }

  for(int i=1;i<=n;i++){
  	for(int j=1;j<=m;j++){
  	 if(v[i][j]=='X'){
  	   up[i][j]=i;
  	   lf[i][j]=j;
  	 }
  	 else{
  	   up[i][j]=up[i-1][j];
  	   lf[i][j]=lf[i][j-1];
  	 }
  	}
  }
   
  queue<array<int,2>> q;
  vector<vector<bool>> vis(n+5,vector<bool>(m+5,0));

  q.push({a,d});
  
  while(!q.empty()){
    int x=q.front()[0];
    int y=q.front()[1];
    q.pop();
    if(v[x][y]=='X') continue;
    if(vis[x][y]) continue;
    vis[x][y]=1;

    if(x>1 && v[x-1][y]!='X' && min(rg[x][y],rg[x-1][y])-max(lf[x][y],lf[x-1][y])-1>=k)
       q.push({x-1,y});
    if(x+1<=n && v[x+1][y]!='X' && min(rg[x][y],rg[x+1][y])-max(lf[x][y],lf[x+1][y])-1>=k)
       q.push({x+1,y});
    if(y+1<=m && v[x][y+1]!='X' && min(dw[x][y],dw[x][y+1])-max(up[x][y],up[x][y+1])-1>=l)
       q.push({x,y+1});
    if(y>1 && v[x][y-1]!='X' && min(dw[x][y],dw[x][y-1])-max(up[x][y],up[x][y-1])-1>=l)
       q.push({x,y-1});
  }

  if(vis[t_a][t_b]) cout << "YES\n";
  else cout << "NO\n";  
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}	

Compilation message (stderr)

Main.cpp: In function 'void _()':
Main.cpp:89:13: warning: 't_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |   if(vis[t_a][t_b]) cout << "YES\n";
      |             ^

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