（递归）打死我也不说！ -一个渣渣

文章目录

输出格式:
输出样例1:
输出样例2:

注意总结：

nextInt()只读取数值，回车"\n"不会读取，nextLine()会读取"\n"，并结束

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

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

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

注意:

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

输入格式:

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

输出格式:

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

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

输入样例1:

输出样例1:

1 3
5 4
13

输入样例2:

5 5
12345
adswa
54321
dswys
aaaaa

输出样例2:

DSWYBS

思路：

先循环找到D，保存D的坐标，然后从D点开始递归（因为题目中说至多藏有一串“DSWYBS”），找到符合条件的字串序列，到S点再保存下S点的坐标就OK了！

注意字串数组下标从0开始，这是为什么递归函数n!=6的原因！

        sta[0] = "D";
       sta[1] = "S";
       sta[2] = "W";
       sta[3]= "Y";
       sta[4] = "B";
       sta[5] = "S";

代码中还有解释！

代码如下：

import java.util.*;
public class 打死我也不说 {
	static int N,M;
	static String[][] array;
	static int[][] location = new int[2][2];//记录D和S的位置
	//如果不区分大小写，则将sta设为二维数组，第二列存放dswybs
	static String[] sta = new String[6];//存放字符串DSWYBS
	static boolean flag = false;
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		sta[0] = "D";  
		sta[1] = "S"; 
		sta[2] = "W";
		sta[3]= "Y"; 
		sta[4] = "B"; 
		sta[5] = "S"; 
		M = sc.nextInt();
		N = sc.nextInt();
		//nextInt()只读取数值，剩下"\n"还没有读取，nextLine()会读取"\n"，并结束
		sc.nextLine();//读取回车，否则将被数组读取造成每行最后一个没有的现象
		array = new String[M][N];
		for(int i=0;i<M;i++){
				String tmp = sc.nextLine();
				//array[i] = tmp.split("");不能这么用，每行最后一个字符会读不到
				for(int j=0;j<N;j++){
					array[i][j]=String.valueOf(tmp.charAt(j));
				}
		}
		for(int i=0;i<M;i++)
			for(int j=0;j<N;j++) {
				if("D".equals(array[i][j])) {//找到D
					try {
						recursion(i, j ,1);//利用递归去确定字符串DSWYBS,到S后将flag置为true,1代表第一个字符D
					}catch(Exception e) {}
					if(flag == true) {
						location[0][0] = i;
						location[0][1] = j;
						break;
					}
				}
			}
		if(flag) {
			int Sum = location[0][0] + location[0][1] + location[1][0] +location[1][1];
			System.out.println(location[0][0]+" "+location[0][1]);
			System.out.println(location[1][0]+" "+location[1][1]);
			System.out.println(Sum);
		}
		else {
			System.out.println("DSWYBS");
		}
	}
	public static void recursion(int x, int y, int n) throws Exception {//判断D点的周围一圈的点，递归搜索
		if(n!=6) {
			if(x>=1 && y>=1) {
				if(array[x-1][y-1].equals(sta[n]))//等于下一个字符就在递归搜索下一个字符（n+1）
					recursion(x-1, y-1, n+1);
			}
			if(x>=1){
				if(array[x-1][y].equals(sta[n]))
					recursion(x-1, y, n+1);
			}
			if(x>=1 && y+1<N) {
				if(array[x-1][y+1].equals(sta[n]))
					recursion(x-1, y+1, n+1);
			}
			if(y>1){
				if(array[x][y-1].equals(sta[n]))
					recursion(x, y-1, n+1);
			}
			if(y+1<N){
				if(array[x][y+1].equals(sta[n]))
					recursion(x, y+1, n+1);
			}
			if(x+1<M && y>=1) {
				if(array[x+1][y-1].equals(sta[n]))
					recursion(x+1, y-1, n+1);
			}
			if(x+1<M) {
				if(array[x+1][y].equals(sta[n]))
					recursion(x+1, y, n+1);
			}
			if(x+1<M && y+1<N) {
				if(array[x+1][y+1].equals(sta[n]))
					recursion(x+1, y+1, n+1);
			}
		}
		else {
			location[1][0] = x;
			location[1][1] = y;
			flag = true;
			throw new Exception();
		}
	}
}

转载自原文链接, 如需删除请联系管理员。

原文链接：（递归）打死我也不说！，转载请注明来源！