제출 #1328306

#제출 시각아이디문제언어결과실행 시간메모리
1328306trideserToy (CEOI24_toy)C++20
0 / 100
0 ms356 KiB
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
	int W, H, K, L;
	cin >> W >> H >> K >> L;
	int x0, y0, x1, y1;
	cin >> x0 >> y0 >> x1 >> y1;
	int r = y0;
	int c = x1;
	vector<string> map(H);
	for(int i = 0; i < H; i++) cin >> map[i];
	vector<vector<int>> horizontal(H, vector<int>(W));
	for(int i = 0; i < W - 1; i++) {
		int obstacles = 0;
		for(int j = 0; j < L; j++) {
			obstacles += map[j][i] == 'X';
			obstacles += map[j][i + 1] == 'X';
		}
		if(obstacles == 0) horizontal[0][i] = 1;
		for(int j = 0; j < H - L; j++) {
			obstacles += map[j + L][i] == 'X';
			obstacles -= map[j][i] == 'X';
			obstacles += map[j + L][i + 1] == 'X';
			obstacles -= map[j][i + 1] == 'X';
			if(obstacles == 0) horizontal[j + 1][i] = 1;
		}
	}
	vector<vector<int>> vertical(H, vector<int>(W));
	for(int i = 0; i < H - 1; i++) {
		int obstacles = 0;
		for(int j = 0; j < K; j++) {
			obstacles += map[i][j] == 'X';
			obstacles += map[i + 1][j] == 'X';
		}
		//cout << obstacles << "\n";
		if(obstacles == 0) vertical[i][0] = 1;
		for(int j = 0; j < W - K; j++) {
			obstacles += map[i][j + K] == 'X';
			obstacles -= map[i][j] == 'X';
			obstacles += map[i + 1][j + K] == 'X';
			obstacles -= map[i + 1][j] == 'X';
			//cout << i << " " << j << " " << obstacles << "\n";
			if(obstacles == 0) vertical[i][j + 1] = 1;
		}
	}
	for(int i = 0; i < W; i++) {
		for(int j = 1; j < H; j++) {
			horizontal[j][i] += horizontal[j - 1][i];
		}
	}
	for(int i = 0; i < H; i++) {
		for(int j = 1; j < W; j++) {
			vertical[i][j] += vertical[i][j - 1];
		}
	}
	for(vector<int> vec : horizontal) {
		for(int b : vec) { //cout << b;}
		}
		//cout << "\n";
	}
	//cout << "\n";
	for(vector<int> vec : vertical) {
		for(int b : vec) {//cout << b;
		}
		//cout << "\n";
	}
	//cout << "\n";
	vector<vector<bool>> reachable(H, vector<bool>(W));
	queue<pair<int, int>> q;
	q.push(make_pair(r, c));
	while(!q.empty()) {
		int a, b;
		tie(a, b) = q.front();
		q.pop();
		if(reachable[a][b]) continue;
		reachable[a][b] = true;
		int lhindex = a;
		int fhindex = a - L;
		int lvindex = b;
		int fvindex = b - K;
		int rl = horizontal[lhindex][b];
		int rf = fhindex < 0 ? 0 : horizontal[fhindex][b];
		//cout << a << " " << b << " " << fvindex << " " << lvindex << "\n";
		if(rl != rf) {
			//cout << a << " " << b << " " << "R\n";
			q.push(make_pair(a, b + 1));
		}
		if(b >= 1) {
			int ll = horizontal[lhindex][b - 1];
			int lf = fhindex < 0 ? 0 : horizontal[fhindex][b - 1];
			if(ll != lf) {
				//cout << a << " " << b << " " << "L\n";
				q.push(make_pair(a, b - 1));
			}
		}
		int dl = vertical[a][lvindex];
		int df = fvindex < 0 ? 0 : vertical[a][fvindex];
		if(dl != df) {
			//cout << a << " " << b << " " << "D\n";
			q.push(make_pair(a + 1, b));
		}
		if(a >= 1) {
			int ul = vertical[a - 1][lvindex];
			int uf = fvindex < 0 ? 0 : vertical[a - 1][fvindex];
			if(ul != uf) {
				//cout << a << " " << b << " " << "U\n";
				q.push(make_pair(a - 1, b));
			}
		}
	}
	for(int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++) {
			if(map[i][j] == '*') {
				cout << (reachable[i][j] ? "yes\n" : "no\n");
				return 0;
			}
		}
	}
	return 0;
}
#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...