Submission #1087827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087827		mychecksedad	Toy (CEOI24_toy)	C++17	0 / 100	1 ms	860 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define en cout << '\n'
#define vi vector<int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 1500+100;


int n, m, k, l, xh, yh, xv, yv, pref[N][N], H[N][N], V[N][N], vis[N][N];
string s[N];
int arr[4][2]={
	{0, 1},
	{1, 0},
	{-1, 0},
	{0, -1}
};
int get(int r1, int r2, int c1, int c2){
	return pref[r2][c2] - pref[r1 - 1][c2] - pref[r2][c1 - 1] + pref[r1 - 1][c1 - 1];
}
void solve(){
	cin >> m >> n >> k >> l;	
	cin >> xh >> yh >> xv >> yv;
	++xh, ++yh, ++xv, ++yv;
	for(int i = 1; i <= n; ++i){
		cin >> s[i];
		s[i] = " " + s[i];
	}
	for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) pref[i][j] = 0;
	for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) H[i][j] = V[i][j] = vis[i][j] = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
			if(s[i][j] == 'X') ++pref[i][j];
		}
	}
	H[xh][yh] = 1;
	queue<pii> q;
	q.push({xh, yh});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx <= n && ny + k - 1 <= m && H[nx][ny] == 0){
				if(get(nx, nx, ny, ny + k - 1) == 0){
					H[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}
	V[xv][yv] = 1;
	q.push({xv, yv});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx + l - 1 <= n && ny <= m && V[nx][ny] == 0){
				if(get(nx, nx+l-1, ny, ny) == 0){
					V[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}

	for(int i = n; i >= 1; --i){
		for(int j = m; j >= 1; --j){
			if(i >= l){
				if(get(i - l + 1, i, j, j) == 0 && V[i - l + 1][j]) V[i][j] = 1;
			}
			if(j >= k){
				if(get(i, i, j - k + 1, j) == 0 && H[i][j - k + 1]) H[i][j] = 1;
			}
		}
	}

	vis[xh][yv] = 1;
	q.push({xh, yv});
	while(!q.empty()){
		int x = q.front().ff;
		int y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; ++i){
			int nx = x + arr[i][0];
			int ny = y + arr[i][1];
			if(nx > 0 && ny > 0 && nx <= n && ny <= m && V[nx][ny] == 1 && H[nx][ny] == 1 && !vis[nx][ny]){
				vis[nx][ny] = 1;
				q.push({nx, ny});
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(s[i][j] == '*' && vis[i][j]){
				cout << "YES";
				return;
			}
		}
	}
	cout << "NO";
}

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	return 0;
}

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