打死我也不说（深度优先搜索）

打死我也不说（深度优先搜索）

题目描述：

梗：最好的密电码是啥？ 是“打死我也不说！”这样，即使帮我们传送密电码的猪队友被敌人抓住严刑拷打，我们也不用担心泄露秘密。

现在稍微改进一下，我们把“打死我也不说”的拼音首字母“DSWYBS”藏在一个矩阵里，而代表“打”的字母D和代表“说”的字母S所在的行列下标之和即是密码。

对于给定的矩阵，请判断其中是否藏有“DSWYBS”，如果有，给出首末两个字母的下标并计算密码；如果没有，打印一行“DSWYBS”。

注意:

• 若藏有“DSWYBS”，则这串字母必是沿行、列或斜45度方向依次排列的。
• 题目保证输入的矩阵至多藏有一串“DSWYBS”。
• 矩阵左上角下标为（0,0）。
• 区分大小写。
• 题目保证输入的矩阵不含有类似这样的排列（即：仅有DSWYB五个字母，但是字母B与S相邻，可组成DSWYBS的排列 ） ：

DSB
 WY
1
2

输入格式:

第一行给出两个整数M、N（均不大于15、不小于4），接下来M行，每行有N个字母或数字，以换行结束。

输出格式:

如果输入矩阵中藏有“DSWYBS”，则输出三行，第一行和第二行分别是首字母D的下标和末字母S的下标，先行下标后列下标，以一个空格间隔。第三行给出两个字母四项下标值之和。

如果没藏有该串字母，则打印一行“DSWYBS”

输入样例1:

8 10
0x00z000d0
00aD00s000
00b0SWk000
000wcY000s
00000B0000
0000S00000
0000000000
0000000000
1
2
3
4
5
6
7
8
9

输出样例1:

1 3
5 4
13
1
2
3

输入样例2:

5 5
12345
adswa
54321
dswys
aaaaa
1
2
3
4
5
6

输出样例2:

DSWYBS
1

思路：

这道题一开始以为是只要按顺序找到这6个字母就行了，最后看题意是沿行、列或斜45度方向依次排列的，这样就不可以用简单的遍历来寻找了，得使用深度优先搜索。定义一个数组ch存DSWYBS来与数组中找到的每个字母对照，当找到第一个字母时，进行深搜，遍历八个方向，直到6个字母找齐后将第6个字母得下标存起来，返回主函数，将第一个字母的下标存起来，按照要求输出对应的就行了。

代码：

#include
int n,m,flag=0;  //flag用于标记是否全部找到 6 个字母 
int x1,y1,x2,y2; //记录坐标的变量  
char ch[7]={'1','D','S','W','Y','B','S'}; //对照数组 
char s[20][20]; //存放密电 

void dfs(int x,int y,int step)
{   //深搜  
	int tx,ty;
	//next是八个方向的坐标 
	int next[8][2]={{0,1},{1,0},{0,-1},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
	if(step==6)
	{   //如果找到第 6 个字母 
		x2=x;  //记录第 6 个字母下标 
		y2=y;
		flag=1; //标记为找齐字母 
		return ;  //返回主函数 
	}
	for(int i=0;i<8;i++)
	{   //遍历八个方向 
		tx=x+next[i][0]; //计算下一个坐标 
		ty=y+next[i][1];
		if(tx>=0&&tx<n&&ty>=0&&ty<m&&s[tx][ty]==ch[step+1])
			dfs(tx,ty,step+1); //如果下标都没越界且与对应数组对应，则进行下一步深搜 
	}
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%s",&s[i]);
	for(int i=0;i<n;i++)
	{
		for(int k=0;k<m;k++)
		{
			if(s[i][k]=='D') //找到第一个字符，进行深搜 
				dfs(i,k,1);
			if(flag)
			{   //如果找齐 6 个字母 
				x1=i; //记录第一个字母下标 
				y1=k;
				break;
			}
		}
		if(flag) break; 
	}
	if(flag)
		printf("%d %d\n%d %d\n%d",x1,y1,x2,y2,x1+y1+x2+y2);
	else printf("DSWYBS");
	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