22 河南省赛 - H.旋转水管（暴搜）

https://codeforces.com/gym/103941

题意
给定 4*m 的矩形，第 1 行第 x 列有起点，第 4 行第 y 列有终点。
第 2 行 和 第 3 行 每一个格子中都有一个管子，管子有两种类型，L型 和 I型，可以任意旋转。

问，能否有一个旋转方案使得从起点流出的水经过管子流向终点？

$1\le m\le 10^5，1\le x,y\le m$

思路
这个题场上想的时候就觉得好像可以直接搜，因为管子类型的限制，合法的情况并没有多少种。
但是实现的时候傻逼了。
当时想的是直接记忆化记录每个位置从每个方向是否来过，如果之前来过而此时没有退出的话，说明从这个方向进入这个位置不能到达终点，那么此时就没必要走。
但是这样忽略了一种情况 ，这样的话每个位置可能会重复经过！因为标记每个位置的时候带上了方向，可能有一种路径从一个方向经过了点 (x,y) 旋转了一次管子，后面转一圈回来又经过了这个位置，又旋转了一次管子，这种情况是非法的。
比如这种情况：

  o
L I I I L
I L I I L
o
1
2
3
4

从起点并不能到达 (1,1)，但是经过 (1,2),(2,2),(2,3)…(1,4),(1,3) 之后，又旋转了一次 (1,2) 就能到达 (1,1) 了，是不合法的。

所以需要像平常的 DFS 一样，记录路径，标记从起点到当前点路径上的所有点，不能重复经过，走不通时再回溯回来，恢复现场，消除标记。

在标记路径走的前提下，如果要加记忆化也可以加记忆化。

#include
using namespace std;

const int N = 100010;
int n, m;
char a[4][N];
int st, en, flag;
int f[4][N];
int vis[4][N][4]; 

void dfs(int x, int y, int dir)
{
	if(x == 3 && y == en) flag = 1;
	if(x < 1 || x > 2 || y < 1 || y > n || f[x][y] || flag) return;
	
	if(vis[x][y][dir]) return; //在标记路径的前提下，也可以加上记忆化 
	vis[x][y][dir] = 1;
	
	f[x][y] = 1; //标记当前位置走过 
	
	if(a[x][y] == 'L')
	{
		if(dir == 0) dfs(x, y - 1, 1), dfs(x, y + 1, 3);
		else if(dir == 1) dfs(x - 1, y, 2), dfs(x + 1, y, 0);
		else if(dir == 2) dfs(x, y - 1, 1), dfs(x, y + 1, 3);
		else dfs(x - 1, y, 2), dfs(x + 1, y, 0);
	}
	else
	{
		if(dir == 0) dfs(x + 1, y, 0);
		else if(dir == 1) dfs(x, y - 1, 1);
		else if(dir == 2) dfs(x - 1, y, 2);
		else dfs(x, y + 1, 3);
	}
	f[x][y] = 0; //回溯，恢复现场 
}

void init()
{
	for(int i=1;i<=n;i++){
		f[1][i] = f[2][i] = 0;
		for(int j=0;j<4;j++)
			vis[1][i][j] = vis[2][i][j] = 0;
	}
}

int main(){
	int T; cin >> T;
	while(T--)
	{
		cin >> n >> st >> en;
		for(int i=1;i<=2;i++)
			for(int j=1;j<=n;j++)
				cin >> a[i][j];
		
		init();
		
		flag = 0;
		dfs(1, st, 0);
		if(flag) cout << "YES\n";
		else cout << "NO\n";
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

---

要注意区分 DFS 和 洪水填充：

• 如果可以有回头路走，但是不能回头，所以需要 DFS 标记路径，回溯时恢复现场；
• 而如果不能回头走，就可以用 洪水填充，一直覆盖，不用回溯。