제출 #1345295

#제출 시각아이디문제언어결과실행 시간메모리
1345295thelegendary08Toy (CEOI24_toy)C++17
100 / 100
581 ms348576 KiB
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define vi vector<int>
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl
#define vout(v) cout<<#v<<": "; for(auto u : v)cout<<u<<' '; cout<<endl
using namespace std; 
const int mxn = 1505;
int n,m,h,w,sx,sy,tmp1,tmp2,gx,gy,grid[mxn][mxn],ver[mxn][mxn],hor[mxn][mxn],c1[mxn][mxn],c2[mxn][mxn],vis[mxn][mxn];
vector<pii> adj[mxn][mxn];
signed main(){
	cin>>m>>n>>w>>h>>tmp1>>sx>>sy>>tmp2; f0r(i,n)f0r(j,m){char c; cin>>c; if(c=='X')grid[i][j]=1; else grid[i][j]=0; if(c=='*')gx=i,gy=j;}
	f0r(i,n){
		int sum = 0; f0r(j,w-1)sum+=grid[i][j]; for(int j = 0; j + w - 1 < m; j++){
			sum += grid[i][j+w-1]; if(j>0)sum -= grid[i][j-1]; if(sum == 0)hor[i][j]=1;
		}
	}
	f0r(j,m){
		int sum = 0; f0r(i,h-1)sum+=grid[i][j]; for(int i = 0; i + h - 1 < n; i++){
			sum += grid[i+h-1][j]; if(i>0)sum -= grid[i-1][j]; if(sum==0)ver[i][j]=1; 
		}
	}
	
	f0r(j,m-1){
		int sum = 0;
		f0r(i,n){
			sum += (ver[i][j] & ver[i][j+1]); if(i - h >= 0)sum -= (ver[i-h][j] & ver[i-h][j+1]);
			if(sum > 0)c1[i][j]=1;
		}
	}
	f0r(i,n-1){
		int sum = 0; f0r(j,m){
			sum += (hor[i][j] & hor[i+1][j]); if(j - w >= 0)sum -= (hor[i][j-w] & hor[i+1][j-w]);
			if(sum > 0)c2[i][j]=1;
		}
	}
	
	f0r(i,n){
		int sum = 0; f0r(j,m-1){
			sum += hor[i][j]; if(j - w + 1 >= 0)sum -= hor[i][j-w+1]; 
			if(sum && c1[i][j])adj[i][j].eb(i,j+1),adj[i][j+1].eb(i,j);
		}
	}
	f0r(j,m){
		int sum = 0; f0r(i,n-1){
			sum += ver[i][j]; if(i - h + 1 >= 0)sum -= ver[i-h+1][j]; 
			if(sum && c2[i][j])adj[i][j].eb(i+1,j),adj[i+1][j].eb(i,j);
		}
	}
	
	queue<pii>q; q.push(mp(sx,sy)); vis[sx][sy] = 1; while(!q.empty()){
		auto [x,y] = q.front(); q.pop(); for(auto [x_,y_] : adj[x][y]){
			if(vis[x_][y_])continue; vis[x_][y_]=1, q.push(mp(x_,y_));
		}
	} if(vis[gx][gy])cout<<"YES"; else cout<<"NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...