結果

問題 No.3599 Queen Moving Query
コンテスト
ユーザー cho435
提出日時 2026-07-30 01:29:26
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,762 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,815 ms
コンパイル使用メモリ 389,484 KB
実行使用メモリ 23,296 KB
最終ジャッジ日時 2026-07-30 01:29:35
合計ジャッジ時間 8,653 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

void solve() {
	int h, w, sx, sy;
	cin >> h >> w >> sx >> sy;
	sx--, sy--;
	vector<string> s(h);
	rep(i, 0, h) cin >> s[i];
	vector mn(2, vector(8, vector(h, vector<int>(w, 1e9))));
	deque<array<int, 4>> dq;
	rep(d, 0, 8) {
		dq.push_back({sx, sy, (int)d, 1});
		mn[1][d][sx][sy] = 1;
	}
	vector<int> dx = {0, 1, 1, 1, 0, -1, -1, -1};
	vector<int> dy = {1, 1, 0, -1, -1, -1, 0, 1};
	auto check = [&](int x, int y) {
		return 0 <= x && x < h && 0 <= y && y < w && s[x][y] == '.';
	};
	while (!dq.empty()) {
		auto [x, y, d, f] = dq.front();
		dq.pop_front();
		if (f > mn[f & 1][d][x][y]) continue;
		int nd = mn[f & 1][d][x][y];
		{
			int nx = x + dx[d], ny = y + dy[d];
			if (check(nx, ny) && chmin(mn[nd & 1][d][nx][ny], nd)) {
				dq.push_front({nx, ny, d, nd});
			}
		}
		nd++;
		for (d = 0; d < 8; d++) {
			int nx = x + dx[d], ny = y + dy[d];
			if (check(nx, ny) && chmin(mn[nd & 1][d][nx][ny], nd)) {
				dq.push_back({nx, ny, d, nd});
			}
		}
	}
	vector cs(2, vector(h, vector<int>(w, 1e9)));
	rep(f, 0, 2) rep(d, 0, 8) rep(i, 0, h) rep(j, 0, w) {
		chmin(cs[f][i][j], mn[f][d][i][j]);
	}
	int q;
	cin >> q;
	while (q--) {
		int qx, qy, t;
		cin >> qx >> qy >> t;
		qx--, qy--;
		if (cs[t & 1][qx][qy] > t) cout << "No\n";
		else cout << "Yes\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0