Description

一个 $H$ 行 $W$ 列的网格，其内部有一个由两部分组成的金属物体：一个 $1$ 行 $K$ 列的横部和一个 $L$ 行 $1$ 列的纵部。若称无障碍物的方格为空格，则这两部分仅可以在空格上水平或垂直滑动，并始终重叠在一个空格上。

问是否能将金属物体的重叠部分移动到指定的目标空格上。

Solution

如果金属物体的重叠部分一定（若存在），其横部和纵部可以任意滑动，则不存在两种可行的放置方式且相互之间不能通过滑动转化。

• 因此可以用重叠部分的方格来表示金属物体的位置。

至于金属物体的移动，给朕上图！

1. 金属物体若要经过左侧地形，则纵部必须满足 $2\le L\le3$；
2. 金属物体若要经过右侧地形，则横部必须满足 $2\le K\le3$。

那么设金属物体位于空格 $X$，包含 $X$ 的一列连续空格的最大集合为 $A$，包含 $X$ 的一行连续空格的最大集合为 $B$（$X$ 一定时，$A,B$ 一定），

• 金属物体若要左（右）移，设 $X$ 左（右）边的空格为 $Y$，包含 $Y$ 的一列连续空格的最大集合为 $C$，则应满足 $\left|A\cap C\right|\ge L$；
• 金属物体若要上（下）移，设 $X$ 上（下）边的空格为 $Z$，包含 $Z$ 的一行连续空格的最大集合为 $D$，则应满足 $\left|B\cap D\right|\ge K$；

如果在 dfs 的同时求 $A\cap C,B\cap D$，Subtask #5 会有十几个超时。啊！那么显然就是没看数据范围，应当先用前缀和预处理出每个 $X$ 的 $\left|A\right|,\left|B\right|$，然后从初始位置 dfs 就行了。

代码里换成了队列实现的 bfs，常数稍微小点，时间复杂度 $\mathcal O(HW)$。

Code

#include <iostream>
#include <queue>
#define fi first
#define se second
using namespace std;
const int N = 1503;
int w, h, k, l, dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
int lft[N][N], rt[N][N], top[N][N], bot[N][N];
pair <int, int> x;
queue <pair <int, int>> q;
char mmp[N][N];
int read(){
	int x = 0;
	char a = getchar();
	while(a < '0' || '9' < a) a = getchar();
	while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
	return x;
}
void write(int x){
	if(x > 9) write(x / 10);
	putchar(x % 10 | 48);
}
bool bfs(){
	while(!q.empty()){
		x = q.front();
		q.pop();
		if(mmp[x.fi][x.se] == '*') return 1;
		if(mmp[x.fi][x.se] == '+') continue;
		mmp[x.fi][x.se] = '+';
		for(int i = 0; i <= 3; ++ i)
			if(mmp[x.fi + dx[i]][x.se + dy[i]] == '.' || mmp[x.fi + dx[i]][x.se + dy[i]] == '*')
				if(dx[i]){
					if(min(rt[x.fi][x.se], rt[x.fi + dx[i]][x.se]) + min(lft[x.fi][x.se], lft[x.fi + dx[i]][x.se]) > k)
						q.push(make_pair(x.fi + dx[i], x.se));
				}
				else if(min(bot[x.fi][x.se], bot[x.fi][x.se + dy[i]]) + min(top[x.fi][x.se], top[x.fi][x.se + dy[i]]) > l)
					q.push(make_pair(x.fi, x.se + dy[i]));
	}
	return 0;
}
int main(){
	w = read(), h = read(), k = read(), l = read();
	read(), x.fi = read() + 1, x.se = read() + 1, read(); //交点坐标
	for(int i = 1; i <= h; ++ i) scanf("%s", mmp[i] + 1);
	for(int i = 1; i <= h; ++ i)
		for(int j = 1; j <= w; ++ j)
			if(mmp[i][j] != 'X')
				lft[i][j] = lft[i][j - 1] + 1,
				top[i][j] = top[i - 1][j] + 1;
	for(int i = h; i >= 1; i --)
		for(int j = w; j >= 1; j --)
			if(mmp[i][j] != 'X')
				rt[i][j] = rt[i][j + 1] + 1,
				bot[i][j] = bot[i + 1][j] + 1;
	q.push(x);
	fputs(bfs()? "YES": "NO", stdout);
	return 0;
}