Submission #1208141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208141		NK_	Toy (CEOI24_toy)	C++20	0 / 100	569 ms	1114112 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back

using str = string;
template<class T> using V = vector<T>;
// template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
using vs = V<str>;
using vi = V<int>;

const int nax = 305, wax = 11;
bitset<wax * wax> pos[nax][nax];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int R, C, W, L; cin >> C >> R >> W >> L;

	int xw, yw, xl, yl; cin >> xw >> yw >> xl >> yl; 
	// --xw, --yw, --xl, --yl;

	vs A(R); for(auto& x : A) cin >> x;

	int er, ec; for(int r = 0; r < R; r++) for(int c = 0; c < C; c++) {
		if (A[r][c] == '*') {
			er = r, ec = c;
			A[r][c] = '.';
		}
	}

	for(int i = 0; i < nax; i++) for(int j = 0; j < nax; j++) {
		pos[i][j].reset();
	}	

	V<vi> hor(R, vi(C)), ver(R, vi(C));
	for(int i = 0; i < R; i++) {
		for(int j = C - 1; j >= 0; j--) {
			if (j + 1 < C) hor[i][j] = hor[i][j + 1];
			if (A[i][j] == '.') hor[i][j]++;
			if (A[i][j] == 'X') hor[i][j] = 0;
			// cout << hor[i][j] << " ";
		}
		// cout << endl;
	}

	for(int j = 0; j < C; j++) {
		for(int i = R - 1; i >= 0; i--) {
			if (i + 1 < R) ver[i][j] = ver[i + 1][j];
			if (A[i][j] == '.') ver[i][j]++;
			if (A[i][j] == 'X') ver[i][j] = 0;
			// cout << ver[i][j] << " ";
		}	
		// cout << endl;
	}	

	bool ans = 0;
	function<void(int, int, int, int)> dfs = [&](int r, int c, int rx, int cx) {
		// cout << r << " " << c << " " << rx << " " << cx << endl;
		if (pos[r][c][rx * wax + cx]) return;
		pos[r][c][rx * wax + cx] = 1;

		int rw = r + rx, cw = c, rl = r, cl = c + cx;
		// cout << rw << " " << cw << " | " << rl << " " << cl << endl;
		if (rw == er && cl == ec) ans = 1;

		// move vertical left
		if (cl - 1 >= 0 && cx - 1 >= 0 && ver[rl][cl - 1] >= L) {
			dfs(r, c, rx, cx - 1);
		}

		// move vertical right
		if (cl + 1 < C && cx + 1 < W && ver[rl][cl + 1] >= L) {
			dfs(r, c, rx, cx + 1);
		}

		// move vertical up
		if (rl - 1 >= 0 && rx + 1 < L && ver[rl - 1][cl] >= L) {
			dfs(r - 1, c, rx + 1, cx);
		}

		// move vertical down
		if (rl + 1 < R && rx - 1 >= 0 && ver[rl + 1][cl] >= L) {
			dfs(r + 1, c, rx - 1, cx);
		}

		// move horizontal up
		if (rw - 1 >= 0 && rx - 1 >= 0 && hor[rw - 1][cw] >= W) {
			dfs(r, c, rx - 1, cx);
		}

		// move horizontal down
		if (rw + 1 < R && rx + 1 < L && hor[rw + 1][cw] >= W) {
			dfs(r, c, rx + 1, cx);
		}

		// move horizontal left
		if (cw - 1 >= 0 && cx + 1 < W && hor[rw][cw - 1] >= W) {
			dfs(r, c - 1, rx, cx + 1);
		}

		// move horizontal right
		if (cw + 1 < C && cx - 1 >= 0 && hor[rw][cw + 1] >= W) {
			dfs(r, c + 1, rx, cx - 1);
		}
	};	

	dfs(yl, xw, yw - yl, xl - xw);

	cout << (ans ? "YES" : "NO") << nl;

	exit(0-0);
}

// Breathe In, Breathe Out

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