結果

問題 No.3599 Queen Moving Query
コンテスト
ユーザー pengin_2000
提出日時 2026-07-24 23:04:16
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,708 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 123 ms
コンパイル使用メモリ 41,008 KB
実行使用メモリ 6,912 KB
最終ジャッジ日時 2026-07-24 23:04:24
合計ジャッジ時間 2,680 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
char s[100005], ss[100005];
int dp[100005][2];
int q[500005], left, right;
int checked[100005][2][4];
int main()
{
	int h, w, sx, sy;
	scanf("%d %d %d %d", &h, &w, &sx, &sy);
	sx--;
	sy--;
	int i, j, k;
	for (i = 0; i < h; i++)
	{
		scanf("%s", ss);
		for (j = 0; j < w; j++)
			s[w * i + j] = ss[j];
	}
	int di[8] = { -1,-1,-1,0,1,1,1,0 };
	int dj[8] = { -1,0,1,-1,1,0,-1,1 };
	int ii, jj, d;
	for (i = 0; i < h * w; i++)
		dp[i][0] = dp[i][1] = 2e9;
	for (i = 0; i < h * w; i++)
		for (j = 0; j < 4; j++)
			checked[i][0][j] = checked[i][1][j] = 0;
	left = right = 0;
	for (k = 0; k < 8; k++)
	{
		for (ii = sx, jj = sy;;)
		{
			ii += di[k];
			jj += dj[k];
			if (ii < 0 || jj < 0 || ii >= h || jj >= w)
				break;
			if (s[w * ii + jj] == '#')
				break;
			if (dp[w * ii + jj][1] > 1)
			{
				dp[w * ii + jj][1] = 1;
				q[right++] = 2 * w * ii + 2 * jj + 1;
			}
			checked[w * ii + jj][1][k % 4]++;
		}
	}
	while (left < right)
	{
		i = q[left++];
		d = i % 2;
		i /= 2;
		j = i % w;
		i /= w;
		for (k = 0; k < 8; k++)
		{
			if (checked[w * i + j][1 - d][k % 4] > 1)
				continue;
			for (ii = i, jj = j;;)
			{
				ii += di[k];
				jj += dj[k];
				if (ii < 0 || jj < 0 || ii >= h || jj >= w)
					break;
				if (s[w * ii + jj] == '#')
					break;
				if (dp[w * ii + jj][1 - d] > dp[w * i + j][d] + 1)
				{
					dp[w * ii + jj][1 - d] = dp[w * i + j][d] + 1;
					q[right++] = 2 * w * ii + 2 * jj + 1 - d;
				}
				checked[w * ii + jj][1 - d][k % 4]++;
			}
		}
	}
	int q;
	scanf("%d", &q);
	int gx, gy, t;
	for (i = 0; i < q; i++)
	{
		scanf("%d %d %d", &gx, &gy, &t);
		if (dp[w * (gx - 1) + gy - 1][t % 2] > t)
			printf("No\n");
		else
			printf("Yes\n");
	}
	return 0;
}
0