题解 P13710 NWERC 2023 Klompendans

题解：P13710 [NWERC 2023] Klompendans

原题链接

这一道题，当我看到题目描述的那张图是，就知道是一道标准的搜索。

众所周知搜索分为Breadth-First Search和Depth-First Search（小装一波）。

这道题的类型属于BFS，但是天生反骨的我用的是DFS，但还是有原因的，见下：

题意解释

这道题要求从一个n*n的矩阵的左上角开始，有两种运动方法：

1.从当前瓷砖移动到一个距离当前瓷砖沿一个轴方向 a 格、另一轴方向 b 格的瓷砖。注意：题目没有限定对印的轴和正负移动方向，故达成题目中说的8种方法
（感谢豆包为我答疑解惑），
代码如下（pair的第一个值表示x轴，第二个表示y轴）：

`mova[0] = {a, b};
mova[1] = {a, -b};
mova[2] = {-a, b};
mova[3] = {-a, -b};
mova[4] = {b, a};
mova[5] = {b, -a};
mova[6] = {-b, a};
mova[7] = {-b, -a};

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
2.从当前瓷砖移动到一个距离当前瓷砖沿一个轴方向 c 格、另一轴方向 d 格的瓷砖。同理，8种方法，（代码不展示，自己推一下，这是本题的难点之一）。

 
第一个点可以任选一种移动方法，后面的点必须选前面一个点不同的方案。

 
求一共有多少个点可到达。**注意：题目要求所有可到达的点，不是一条路径上的所有点，一次从一个点出发一次跳跃可到达的点都是合法的，包含在答案之中。**

 
**同时，题目没有限制出发点的做法，所以两种选择可到达的点都包含在答案之中**

 
我之所以使用DFS，是因为一个点的前一个点可能是任意一种情况，也就是说一个点可以同时有两种移动方法，使用BFS记录和处理过于复杂，因此我选择了DFS（当然还主要是<s>懒</s>）。

 
#### 我的代码（58ms AC）
 
`#include <bits/stdc++.h>
#define ll long long
#define LL long long

using namespace std;

const int N=502;
int n,a,b,c,d,ans=0;
bool vis[N][N][2]={<!-- -->0},viss[N][N]={<!-- -->0};//vis[x][y][t]表示（x，y）点是否在t情况下访问过了；viss[x][y]表示（x，y）是否被访问过，用于ans计数
pair<int,int>mova[8],movb[8];//表示两种情况的所有移动方案

bool check(int x,int y){<!-- -->//检查合法性
	return x>0 && y>0 && x<=n && y<=n;
}

void dfs(int x,int y,int t){<!-- -->//（x，y）是点的坐标，t=0时是第一中移动类型，t=2是第二中移动类型
	//检查点是否在图内
	if(!check(x,y)){<!-- -->
		return;
	}
	//如果这个点已经在t状态下被访问过了，就return
	if(vis[x][y][t]){<!-- -->
		return;
	}
	vis[x][y][t]=1;
	//如果这个点在t=0和t=1两个状态都没有被访问过，就是一个新到的点，ans++
	if(!viss[x][y]){<!-- -->
		ans++;
		viss[x][y]=1;
	}
	//去下一个点
	for(int i=0;i<8;i++){<!-- -->
		if(t==0){<!-- -->
			dfs(x+mova[i].first,y+mova[i].second,1);
		}else{<!-- -->
			dfs(x+movb[i].first,y+movb[i].second,0);
		}
	}
}

int main(){<!-- -->
	//输入
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	// 初始化移动A的8个方向
	mova[0] = {<!-- -->a, b};
	mova[1] = {<!-- -->a, -b};
	mova[2] = {<!-- -->-a, b};
	mova[3] = {<!-- -->-a, -b};
	mova[4] = {<!-- -->b, a};
	mova[5] = {<!-- -->b, -a};
	mova[6] = {<!-- -->-b, a};
	mova[7] = {<!-- -->-b, -a};
	// 初始化移动B的8个方向
	movb[0] = {<!-- -->c, d};
	movb[1] = {<!-- -->c, -d};
	movb[2] = {<!-- -->-c, d};
	movb[3] = {<!-- -->-c, -d};
	movb[4] = {<!-- -->d, c};
	movb[5] = {<!-- -->d, -c};
	movb[6] = {<!-- -->-d, c};
	movb[7] = {<!-- -->-d, -c};
	//开始DFS（第一个点有两种选择），中间不需要memset！！！
	dfs(1,1,0);
	dfs(1,1,1);
	//输出
	printf("%lld",ans);
	return 0;
}

完结撒花-！！！