DFS和BFS以及练习题目（未完待续）

DFS和BFS

温馨提示：学习dfs之前最好先了解一下递归的思想。

递归思想

斐波那契

题目分析

题目代码

import java.util.Scanner;
public class Main{
	static long dp[];
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int t = scanner.nextInt();
	dp = new long[61];
	while(t-- > 0) {
		int n = scanner.nextInt();
		System.out.println("Fib("+n+") = "+f(n));
	}
}
private static long f(int n) {
	// TODO Auto-generated method stub	
	if(n==1||n==2) return 1;
	if(n<=0) return 0;
	if(dp[n]!=0) return dp[n];
	dp[n] = f(n-1)+f(n-2);
	return dp[n];
}
}

DFS

DFS基础——图的遍历

迷宫(dfs)

题目分析

这一道题我们可以用dfs也可以用bfs，但是对于迷宫最短路类题目，最好的方法是bfs。通过这道题如果采用dfs来做，需要用到dfs里的回溯和剪枝。

首先分析题意，我们要找从起点到终点的最短路，并且这个最短路的行走路线是字典序最小，其实字典序最小好操作，我们只需要在遍历上下左右四个方向的时候按照字典序从小到大的顺序遍历就行了。即

static char[] direct = {'D','L','R','U'};
static int[] nexty = {0,-1,1,0};
static int[] nextx = {1,0,0,-1};

接下来考虑如何找最短路，对于dfs而言，要找最短路，我必须把当前可走的所有路都遍历结束后，才能确定哪一条路是最短路，对于某一个位置，我当前向左走，标记左边的节点为已遍历过，并且把这个’L’存入，走到终点后我再回退，那么再次回到这个位置时，我会选择其它可以走的方向，那么我们要把左边的节点已遍历过的标记清空，表示没有遍历过，并且把在这里存入的’L’取出。即

for (int i = 0; i < 4; i++) {
		int xx = x + nextx[i];
		int yy = y + nexty[i];
		if(xx >= 0 && xx < n && yy >= 0 && yy < m &&visit[xx][yy] == 0 && map[xx][yy] == '0') {
			visit[xx][yy] = 1;
			path[s] = direct[i];//更新路径
            ......
			dfs(xx, yy, s+1);
			visit[xx][yy] = 0;//回溯 dfs返回的时候，往往需要对之前做的标记进行重置	
		}
	}

解释一下上述代码，for (int i = 0; i < 4; i++)表示四个方向遍历，它遍历的顺序由nextx和nexty数组决定，而我们在最开始就给他规定了遍历的顺序是按字典序从小到大遍历的。然后if语句一是判断下一个位置的坐标是否越界，二是判断下一个位置是否之前被遍历过，三是判断下一个位置是否可以走，都没问题的话我就去走这个位置，然后标记这个位置被走过，并且存入此时走的方向，visit[xx][yy] = 1;path[s] = direct[i];，然后就是进入dfs，那么这里dfs三个参数分别表示下一个位置的x坐标，y坐标，以及走到下一个位置走了几步。dfs结束后，我要给visit标记复原，即visit[xx][yy] = 0;

上述是正常dfs以及回溯的过程，接下来我们要加入剪枝。什么情况下我可以确定这条路一定不会成为答案？也就是这条路的长度超过了我们此时记录的最短路的长度，即

if(s >= step) {
	return;
}

s表示我走到当前节点的步数，step表示此时记录的最短路的长度，我还没有走到终点步数就比最短路长，那么它必然不会成为最短路，所以后面就不需要遍历了，直接返回。

还有第二种剪枝，这个不太好想，也是比较最短路的长度，我们比较的是到达当前位置的长度以及在之前我走到该位置的最短长度。比如有一个点A，我走到这里耗费了s步，但是我之前记录我走到这里耗费了s1步，而s1<s，那么说明我之前走到这里再向后走的路径一定比我现在走到这里再向后走的路径短，那么此时我就没有必要遍历了。即

if(s > dp[x][y]) {
		return;
}

s表示我走到当前节点(x,y)的步数， $d p [x] [y]$ 表示我之前走到该节点的最短路。那么在dfs的过程中我们要更新dp数组，

for (int i = 0; i < 4; i++) {
		int xx = x + nextx[i];
		int yy = y + nexty[i];
		if(xx >= 0 && xx < n && yy >= 0 && yy < m &&visit[xx][yy] == 0 && map[xx][yy] == '0') {
			visit[xx][yy] = 1;
			dp[xx][yy] = Math.min(dp[xx][yy], s+1);//更新dp
			path[s] = direct[i];//更新路径
			dfs(xx, yy, s+1);
			visit[xx][yy] = 0;//回溯 dfs返回的时候，往往需要对之前做的标记进行重置
			//path[s] = '';
		}
	}

在回溯的时候我们只回溯了visit数组，为什么呢?dp数组不需要回溯，因为它记录的就是一个全局的值，即在我所有到达(x,y)点的路径中最短路径的长度。而path数组虽然需要回溯，但是我们在下一个遍历的时候，下一个的值会直接覆盖之前的值，所以不需要特意给他回溯。那么你也可以理解有回溯，即注释的那个地方//path[s] = '';，这里写和不写效果是一样的。

然后我们看当走到终点时，如何处理，

//判断是否走到终点
if(x == n-1 && y == m-1) {
    if(s < step) {//当前步数小于之前的最优值，对结果进行一下记录
        step = s;
        String string = "";
        for (int i = 0; i < s; i++) {
            //System.out.print(" "+path[i] + " ");
            string += path[i];
        }
        //set.add(string);
        result = string;
    }
    //System.out.println();
}

判断一下此时走到终点的路径长度是否小于我之前记录的长度，如果小于，我要更新最短路径长度，以及这条路径每一步走的方向。

最后这道题，给我们的图是一个字符串，我们可以把它转化成二维字符数组，转化细节在shuju函数里。

题目代码

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;

public class Main{
	/*
	 * 在步数最少的前提下，请找出字典序最小的一个作为答案
	 * 如何保证找到的第一个路径一定是字典序最小的
	 * 遍历的时候，按照字典序从小到大的顺序去遍历
	 * D<L<R<U
	 * DDRURRDDDR
	 * DRRURRDDDR
	 * 如何记录我们的路径
	 * bfs 
	 * node{
	 * x，y，path//走到当前节点的路径
	 * }
	 * path
	 */
    static int n = 30;
    static int m = 50;
    static char[][]  map = new char[n][m];
    static char[] direct = {'D','L','R','U'};
    static int[] nexty = {0,-1,1,0};
    static int[] nextx = {1,0,0,-1};
    static int[][] visit = new int[n][m];
    
    //dfs
    static char[] path = new char[n*m+1];
    static int step = n*m+1;
    static String result = "";
    static Set<String> set = new HashSet<String>();
    static int[][] dp = new int[n][m];
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	shuju();
    for(int i=0;i<n;i++){
        Arrays.fill(dp[i], n*m+1);
    }
    sc.close();
    visit[0][0] = 1;
    dfs(0,0,0);
    System.out.println(result);
}
private static void shuju() {
	// TODO Auto-generated method stub
	String string = "01010101001011001001010110010110100100001000101010"
			+"00001000100000101010010000100000001001100110100101"
			+"01111011010010001000001101001011100011000000010000"
			+"01000000001010100011010000101000001010101011001011"
			+"00011111000000101000010010100010100000101100000000"
			+"11001000110101000010101100011010011010101011110111"
			+"00011011010101001001001010000001000101001110000000"
			+"10100000101000100110101010111110011000010000111010"
			+"00111000001010100001100010000001000101001100001001"
			+"11000110100001110010001001010101010101010001101000"
			+"00010000100100000101001010101110100010101010000101"
			+"11100100101001001000010000010101010100100100010100"
			+"00000010000000101011001111010001100000101010100011"
			+"10101010011100001000011000010110011110110100001000"
			+"10101010100001101010100101000010100000111011101001"
			+"10000000101100010000101100101101001011100000000100"    //D -> L -> R -> U
			+"10101001000000010100100001000100000100011110101001"
			+"00101001010101101001010100011010101101110000110101"
			+"11001010000100001100000010100101000001000111000010"
			+"00001000110000110101101000000100101001001000011101"
			+"10100101000101000000001110110010110101101010100001"
			+"00101000010000110101010000100010001001000100010101"
			+"10100001000110010001000010101001010101011111010010"
			+"00000100101000000110010100101001000001000000000010"
			+"11010000001001110111001001000011101001011011101000"
			+"00000110100010001000100000001000011101000000110011"
			+"10101000101000100010001111100010101001010000001000"
			+"10000010100101001010110000000100101010001011101000"
			+"00111100001000010000000110111000000001000000001011"
			+"10000001100111010111010001000110111010101101111000";
			
			//将上面的一大串字符转为数组中存储，且数组为int型，仅存0 和 1两个值 
			int[][] moze= new int[30][50];
			for (int i = 0 ; i < 30 ; i++) {
				for(int j = 0 ; j < 50 ; j++) {
					map[i][j] = string.charAt(i*50+j); //
				}
			}
}
private static void dfs(int x, int y, int s) {//s当前已经走的步数  走的路径的方向path[i] 表示第i步走的方向
	/* 剪枝
	 * 1.s走到x，y所需要的步数，step当前记录的走完迷宫所需要的最短的步数，s>step return
	 * 2.dp[x][y] 当前走到x，y点所需要的最短距离，s>dp[x][y] return
	 * 
	 * 
	 * dfs{
	 * 1.剪枝
	 * 2.回溯
	 * 3.递归
	 * 
	 * }
	 */
	//剪枝操作
	if(s >= step) {
		return;
	}
	if(s > dp[x][y]) {
		return;
	}
	//判断是否走到终点
	if(x == n-1 && y == m-1) {
		//System.out.print("---" + x + " " + y + " ");
		if(s < step) {//当前步数小于之前的最优值，对结果进行一下记录
			step = s;
			String string = "";
			for (int i = 0; i < s; i++) {
				//System.out.print(" "+path[i] + " ");
				string += path[i];
			    
			}
			//set.add(string);
			result = string;
		}
		//System.out.println();
	}
	for (int i = 0; i < 4; i++) {
		int xx = x + nextx[i];
		int yy = y + nexty[i];
		if(xx >= 0 && xx < n && yy >= 0 && yy < m &&visit[xx][yy] == 0 && map[xx][yy] == '0') {
			visit[xx][yy] = 1;
			dp[xx][yy] = Math.min(dp[xx][yy], s+1);//更新dp
			path[s] = direct[i];//更新路径
			dfs(xx, yy, s+1);
			visit[xx][yy] = 0;//回溯 dfs返回的时候，往往需要对之前做的标记进行重置
			
		}
	}
}
}

全球变暖

题目分析

首先要明白这道题求啥，对于一块陆地“#”，如果它的上下左右任何一个相邻位置有还用“.”，那么这块陆地就会变成海洋。但是要注意，变成海洋后的陆地不会对周围陆地产生影响，比如下面这种情况，第二行的“#”都会被淹没变成海洋“.”，第二列和第四列的“#”都会被淹没变成海洋“.”，但是第三行第三列和第四行第三列的“#”不会被淹没。

.	.	.	.
.	#	#	#
.	#	#	#
.	#	#	#

考虑用dfs遍历整个图。对于当前位置来说，如果他是陆地，并且之前没有被遍历过，那么就从这个地方进入dfs，这里的ans表示被完全淹没的岛屿数。flag表示当前遍历的这块岛屿有没有被淹没。flag为0表示被完全淹没了，那么ans对应加1。

int ans = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if(map[i][j] == '#' && visit[i][j] == 0) {
            flag = 0;
            dfs(i,j);
            if(flag == 0) {
                ans++;
            }
        }
    }
}

接下来看dfs的过程，进来之后，首先把当前位置标志为已经被遍历过。遍历这个位置上下左右四个方向，如果四个方向的值都为“#”那么这个地方不会被淹没，也就意味着这个岛屿不会被淹没，flag就标记为1。然后接着去遍历这个岛屿的其它陆地。如果下一个陆地没有被遍历过，则进入继续遍历。

private static void dfs(int i, int j) {
	visit[i][j] = 1;
	if(map[i][j+1]=='#'&&map[i][j-1]=='#'&&map[i-1][j]=='#'&&map[i+1][j]=='#') {
		flag = 1;
	}
	for (int k = 0; k < 4; k++) {
		int x = i + nextx[k];//nextx nexty
		int y = j + nexty[k];
		if(visit[x][y] == 0&&map[x][y]=='#') {
			dfs(x, y);
		}
	}
}

注意上述代码在找相邻节点的时候我没有进行越界判断，是因为我在设数组的时候给它设置了边界，即下标范围是从1~n，那么开数组的时候开大两维，即便1-1=0，也没关系，即便n+1=n+1，也不会越界。当然，你也可以按照正常大小开数组，但是如果是这样的话，一定要加上越界判断。

map = new char[n+2][n+2];
visit = new int[n+2][n+2];
for (int i = 1; i <= n; i++) {
    map[i] = (" "+scanner.next()+" ").toCharArray();
}

题目代码

import java.util.Scanner;
public class Main {
	static int flag=0;
	static int[][] visit;
	static char[][] map;
	static int[] nexty = {0,-1,1,0};
    static int[] nextx = {1,0,0,-1};
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	map = new char[n+2][n+2];
	visit = new int[n+2][n+2];
	for (int i = 1; i <= n; i++) {
		map[i] = (" "+scanner.next()+" ").toCharArray();
	}
	
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if(map[i][j] == '#' && visit[i][j] == 0) {
				flag = 0;
				dfs(i,j);
				if(flag == 0) {
					ans++;
				}
			}
		}
	}
	System.out.println(ans);
}
private static void dfs(int i, int j) {
	visit[i][j] = 1;
	if(map[i][j+1]=='#'&&map[i][j-1]=='#'&&map[i-1][j]=='#'&&map[i+1][j]=='#') {
		flag = 1;
	}
	for (int k = 0; k < 4; k++) {
		int x = i + nextx[k];//nextx nexty
		int y = j + nexty[k];
		if(visit[x][y] == 0&&map[x][y]=='#') {
			dfs(x, y);
		}
	}
}
}

仙境诅咒

问题描述

在一片神秘的仙境中，有N位修仙者，他们各自在仙境中独立修炼，拥有自己独特的修炼之道和修炼之地,修仙者们彼此之间相互尊重、和谐相处。

然而，有一天，仙境的主宰者妮妮(第一位修仙者)受到了诅咒，该诅咒会向距离妮妮不超过D的范围内的修仙者传播。也就是说，如果一个修仙者被诅咒，那么在距离他不超过D的范围内的所有修仙者都会被诅咒。

现在，你需要预测哪些修仙者最终会被诅咒，以便及时采取措施，保护仙境的和平与安宁。

输入格式

第一行输入一个正整数 $N(1<N≤10^3)$ ，表示仙境中有N位修仙者。

接下来N行，每行两个实数 $X_i$ 和 $Y_i$ $ (-10^{3≤X_i,Y_i≤10}3) $，表示第 i 位修仙者的坐标$ (X_i,Y_i)$。第一位修仙者即仙境的主宰者妮妮。

最后一行输入一个正整数 $D (1<=D<= 10^3)$ ，表示诅咒传播的范围。

输出格式

输出N行，每行一个整数，第i行的整数为1表示第i位修仙者最终被诅咒，为0则表示第i位修仙者没有被诅咒。

样例输入

样例输出

题目分析

距离被诅咒者距离不超过D是其它修仙者都会被诅咒感染，也就是我可以从当前被诅咒者走到距离不超过D的其它修仙者。我们可以用数组v[i]=1表示修仙者i已经被诅咒。那么dfs过程代码如下，

private static void dfs(int u) {
	v[u] = 1;
	for(int i = 1;i <=n;i++)
		if(v[i]==0&&dis(u,i)<=d)
			dfs(i);
}

dfs(u)这里的u是已经被诅咒的修仙者，那么v[u]就要被标记为1，然后for循环遍历其它修仙者，如果其它修仙者没有被诅咒，并且与当前节点u的距离小于d，那么说明当前修仙者会被传染成为新的被诅咒者，这个时候就要进入dfs(i)去看i能传染给哪些人。

为什么要判断v[i]==0？防止重复遍历，比如我从节点2进入了节点3，即dfs(2)进入了dfs(3)，在dfs(3)运行时，我判断了dis(2,3)<=d，如果我没有v[i]==0的约束，我会从dfs(3)进入dfs(2)，再从dfs(2)进入dfs(3)，最终产生了死循环。

dis函数就是已知两点坐标求两点距离的公式，很简单，但是注意，这里有开根号，那么会有小数，在定义变量的时候要注意变量的类型。

private static double dis(int u, int v) {
	return Math.sqrt(Math.pow(x[u]-x[v], 2)+Math.pow(y[u]-y[v], 2));
}

最后通过数组v的值是否为1，可以判断当前点是否被传染。

for(int i = 1;i <=n;i++) System.out.println(v[i]==0?0:1);

题目代码

import java.util.Scanner;
public class Main{
	static int n,d;
	static double x[],y[];
	static int v[];
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	n = scanner.nextInt();
	x = new double[n+1];
	y = new double[n+1];
	v = new int[n+1];
	for(int i = 1;i <= n;i++) {
		x[i] = scanner.nextInt();
		y[i] = scanner.nextInt();
	}
	d = scanner.nextInt();
	dfs(1);
	for(int i = 1;i <=n;i++) System.out.println(v[i]==0?0:1);
}
private static void dfs(int u) {
	// TODO Auto-generated method stub
	v[u] = 1;
	for(int i = 1;i <=n;i++)
		if(v[i]==0&&dis(u,i)<=d)
			dfs(i);
}
private static double dis(int u, int v) {
	// TODO Auto-generated method stub
	return Math.sqrt(Math.pow(x[u]-x[v], 2)+Math.pow(y[u]-y[v], 2));
}
}

通过后续的题目希望大家明白，dfs不仅仅是对图的遍历，他还有很多用法。

DFS进阶1——回溯

先说一下回溯的板子

dfs(){
for(......){
    标记信息
    dfs()
    撤销标记
}
}

回溯模板——递归实现排列型枚举

题目分析

其实就是对1~n的数字全排列，这里就可以用dfs去做，1~n全排列我其实是确定每一个位置我应该放哪一个数字，那么dfs的时候就是对位置dfs，dfs(1)表示我现在要选择一个数放在第一个位置，那么可以选择的范围是1~n，

for(int i = 1;i <= n;i++)

且这个数之前没有被选过，那么我们就要用一个数组book[i]标记一下，book[i]=1表示这个数已经被选走了，那么我就不能再选这个数了。

for(int i = 1;i <= n;i++){
    if(book[i]==1) continue;
}

当我遍历到dfs(n+1)时说明我前n个位置都安排完了，那么我就要输出此时的一个排列，我需要知道我此时选出来的数的排列，那么也可以考虑用一个变量保存，这里我使用的是队列。

if(k==n+1) {
		ArrayDeque<Integer> queueTemp = new ArrayDeque<Integer>();
		queueTemp.addAll(queue);
		while(!queueTemp.isEmpty()) {
			System.out.print(queueTemp.pollFirst() + " ");
		}
		System.out.println();
		return;
	}

当我选择数i作为当前位置的数时，我要标记这个数已经被选择了并且把它放入队列，这个位置选好后，我要继续选择下一个位置，所以dfs(k+1)

for(int i = 1;i <= n;i++) {
		if(book[i]==1) continue;
		book[i]=1;
		queue.addLast(i);
		dfs(k+1);
	}

当我从dfs退出后再次回来，说明我要尝试选择其它数了，那么我要把选这个数做的标记都撤销，包括，book数组对应位置置为0和把这个数从队列里面拿出来。

for(int i = 1;i <= n;i++) {
		if(book[i]==1) continue;
		book[i]=1;
		queue.addLast(i);
		dfs(k+1);
		book[i]=0;
		queue.pollLast();
	}

题目代码

import java.util.ArrayDeque;
import java.util.Scanner;
public class Main{
	static ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
	static int book[];
	static int n;
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	n = scanner.nextInt();
	book = new int[n+1];
	dfs(1);
}

private static void dfs(int k) {
	if(k==n+1) {
		ArrayDeque<Integer> queueTemp = new ArrayDeque<Integer>();
		queueTemp.addAll(queue);
		while(!queueTemp.isEmpty()) {
			System.out.print(queueTemp.pollFirst() + " ");
		}
		System.out.println();
		return;
	}
	for(int i = 1;i <= n;i++) {
		if(book[i]==1) continue;
		book[i]=1;
		queue.addLast(i);
		dfs(k+1);
		book[i]=0;
		queue.pollLast();
	}
}
}

代码执行过程模拟

因为初学者对递归不理解，再加上回溯更难理解，所以这里对这个代码进行模拟。以n=3为例，也就是待排列的数字为1，2，3。

上图没有写完，只写了一部分，下图是另一种形式，全都写了完了。

在这里插入图片描述

混境之地5

dfs+回溯+简单剪枝

题目分析

小蓝的起始位置为(A,B)，终点位置为(C,D)，询问能否从起点走到终点。我们注意这是一个矩阵图，每次走的时候可以上下左右四个方向走，一般而言我们只需要从起点去走就可以了，那么我们从起点进入dfs。如下代码，

dfs(A,B);

进入dfs之后，我们先标记 $v i s i t [A] [B] = 1$ ，表示这个点我们已经遍历过了，在遍历图的过程每个节点只能被遍历一遍。然后我们尝试向上下左右四个方向走，对于x,y，向上走就是x+(-1)，y+0，向下走就是x+1，y+0,向左走就是y+(-1)，x+0，向右走就是y+1，x+0。那么我们可以把这里的+(-1)或者+0放在数组里，即

static int []dx = {1,-1,0,0};//x的变化
static int []dy = {0,0,1,-1};//y的变化

然后遍历数组里的值，就可以得到向四个方向走后的坐标。得到坐标之后，我们要判断坐标是否越界，并且还要判断下一个坐标是否之前已经被遍历过，同样我们要判断我们可不可以走向下一个坐标，如果没有越界那么我们就可以走入下一个坐标，对下一个坐标进行递归，即

public static void dfs(int x,int y,int u){
   visit[x][y] = 1;
   for(int i = 0; i < 4; i ++){
       int x1 = x + dx[i];
       int y1 = y + dy[i];
       if(x1<1||x1>n||y1<1||y1>m||visit[x1][y1]==1){
           continue;
       }
       if(c[x1][y1]<=c[x][y]){
           dfs(x1,y1);
       }
   }
}

上述做法是没有考虑可以使用喷气背包的情况，接下来考虑可以使用喷气背包。如果可以使用喷气背包，那么对于下一个我们要遍历的点，如果可以到达它，那么就不使用喷气背包，如果不可以到达，我们就考虑要不要在这个点使用喷气背包，因为我只能使用一次，在哪个点使用可以帮助我们走到终点我们是不确定的。所以每个点我都要尝试一下，那么这就涉及到了回溯，因为对于一个我不能到达的点，我有使用背包和不使用背包两种选择。

因为我们要回溯，所以visit数组要在dfs的附近进行改变，这样dfs结束后方便把visit数组复原。回溯会增加dfs的执行次数，那么如果可以剪枝我们尽量剪枝，这里flag表示我们是否走到了终点，如果走到了直接退出，并且在dfs结束后我们也判断一下，如果之前已经走到过终点了，那么直接退出就行。

public static void dfs(int x,int y,int u){
   if(x==C&&y==D) {
	   flag=1;
	   return;
   }
   for(int i = 0; i < 4; i ++){
       int x1 = x + dx[i];
       int y1 = y + dy[i];
       if(x1<1||x1>n||y1<1||y1>m||visit[x1][y1]==1){
           continue;
       }
       if(c[x1][y1]<=c[x][y]){
    	   visit[x1][y1] = 1;
           dfs(x1,y1,u);
           if(flag==1) return;
           visit[x1][y1] = 0;
       }
       else{
           if(u==1&&c[x1][y1]-c[x][y]<=k){
        	   visit[x1][y1] = 1;
               dfs(x1,y1,0);
               if(flag==1) return;
               visit[x1][y1] = 0;
           }
       }
   }
}

题目代码

import java.util.Scanner;
public class Main{
static int n;
static int m;
static int A;
static int B;
static int C;
static int D;
static int k;
static int [][]visit;
static int [][]c;
static int []dx = {1,-1,0,0};
static int []dy = {0,0,1,-1};
static int flag = 0;
public static void main(String[] args){
   Scanner s = new Scanner(System.in);
   n = s.nextInt();
   m = s.nextInt();
   k = s.nextInt();
   A = s.nextInt();
   B = s.nextInt();
   C = s.nextInt();
   D = s.nextInt();
   c = new int [n+3][m+3];
   visit = new int [n+3][m+3];
   for(int i = 1; i <= n;i ++){
       for(int j = 1; j <= m; j ++){
           c[i][j] = s.nextInt();
           visit[i][j] = -1;
       }
   }
   visit[A][B] = 1;
   dfs(A,B,1);
   if(flag == 1)
       System.out.println("Yes");
   else
       System.out.println("No");
}
public static void dfs(int x,int y,int u){
   if(x==C&&y==D) {
	   flag=1;
	   return;
   }
   for(int i = 0; i < 4; i ++){
       int x1 = x + dx[i];
       int y1 = y + dy[i];
       if(x1<1||x1>n||y1<1||y1>m||visit[x1][y1]==1){
           continue;
       }
       if(c[x1][y1]<=c[x][y]){
    	   visit[x1][y1] = 1;
           dfs(x1,y1,u);
           if(flag==1) return;
           visit[x1][y1] = 0;
       }
       else{
           if(u==1&&c[x1][y1]-c[x][y]<=k){
        	   visit[x1][y1] = 1;
               dfs(x1,y1,0);
               if(flag==1) return;
               visit[x1][y1] = 0;
           }
       }
   }
}
}

通过后续的题目希望大家明白，dfs不仅仅是对图的遍历，他还有很多用法。

最大数字

题目分析

我要求经过一系列操作后可以得到的最大数字，每个操作都有次数限制，我们依次去看这些操作哈，

操作1：假设对于每一位我是从最高位依次向最低位遍历的，对某一位加1，那么加都加了，我们希望把这一位加到最大值也就是9，但是也有可能加不到9，因为我的操作有次数限制，所以就是在9和n之间选一个最小值，那么就是加法的操作次数，如下代码，c表示当前这一位的值，t就是对于当前位来说我能够加的次数，那么n就是可以加的总次数，经过此次操作后，加的总次数要减掉t。j表示前step-1位得到的值，那么遍历完这一位之后，前step位得到的值就是j*10+c+t。

private static void dfs(int step, long j) {
    ......
    int t = Math.min(n, 9 - c);//尽可能的加到9，但是还要考虑我的n可能次数不够了
    n -= t;//减去加操作使用的次数
    dfs(step+1, j*10+c+t);
    n +=t;//回溯，要复原
    ...... 
}

操作2：假设对于每一位我是从最高位依次向最低位遍历的，对某一位减1，那么我要么给他减到9，要么一点都别减。所有只有当我确定我可以减到9时，我才执行减操作。

//减操作，判断是否可以进行，不可以就一步不可进行
if(m > c) {
    m -= c+1;
    dfs(step+1, j*10+9);
    //回溯
    m += c+1;
}

当遍历到最后一位时，此时获得的数字的值就确定了，那么我就拿它和我之间记录的答案比较，取一个最大值就可以了。

if(step==a.length()) {
    ans = Math.max(ans, j);
    return;
}

这里我用字符串存的数字，目的是我可以快速的得到某一位上的值。全部代码如下，

题目代码

import java.util.Scanner;
public class Main {
    static long ans = 0;
    static String a;
    static int n;
    static int m;
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    a = scanner.next();
    n = scanner.nextInt();
    m = scanner.nextInt();
    dfs(0,0);
    System.out.println(ans);
}
private static void dfs(int step, long j) {
    // TODO Auto-generated method stub
	if(step==a.length()) {
		 ans = Math.max(ans, j);
		 return;
	}
    int c = a.charAt(step)-'0';
    //加操作
    int t = Math.min(n, 9 - c);//尽可能的加到9，但是还要考虑我的n可能次数不够了
    n -= t;//减去加操作使用的次数
    dfs(step+1, j*10+c+t);
    //回溯时，不要忘记复原n
    n += t;
    //减操作，判断是否可以进行，不可以就一步不可进行
    if(m > c) {
        m -= c+1;
        dfs(step+1, j*10+9);
        //回溯
        m += c+1;
    }    
}
}

分考场（较难）

题目分析

这个题目稍微难一点，我们要为n个考生分配考场，那么我每次要考虑的是对于第x个考生，我要给他安排在哪一个考场里面，那么我还需要知道我当前使用了哪些考场，并且这些考场里面被安排了哪些考生。我们还要知道哪些考生之间认识。一个一个来解决，设一个数组map[i][j]，如果值为1表示编号为i和编号为j的考生认识，否则就是不认识。设一个变量cnt表示当前我已经使用的考场的个数。设一个数组room[i][j]=k表示在第i个考场里的第j个学生的编号为k。

接下来考虑dfs的过程。x表示当前要安排第x个考生，当前使用的考场数为cnt个

static void dfs(int x, int cnt)

接下来是剪枝，如果当前使用的考场数超过了我之前记录的最小考场数，那么后面就不用遍历了，

if(cnt>=min) return;

然后是终点判断，当n个人都遍历完时，也就是x到了n+1我要看当前使用的考场数是否比我之前记录的最小考场数还小

if(x==n+1){
    min = Math.min(min,cnt);
    return;
}

接下来就是安排考场了，考虑把第x个考生安排在第j个考场，j的取值从1到cnt。那么我要判断，第j个考场的所有人是否有和第x个考生认识的。如果room[j][k]!=0表示第j个考场有第k个考生，并且它的编号是room[j][k]，那么我们要判断这个考生和第x个考生是否认识，即map[x][room[j][k]]==0表示他们不认识。

int j,k;
for(j=1; j<=cnt; j++){
    k=1;
    while(room[j][k]!=0 && map[x][room[j][k]]==0){
        k++;
    }
    ......

while循环退出有两种情况，第一种room[j][k]==0表示我已经把第j个考场的考生都遍历完了，没有和第x个考生认识的人，那么我可以把第x个考生放在第j个考场，即

if(room[j][k]==0){
    room[j][k]=x;//把第x个考生放入第j个考场，并且他是第j个考场的第k位
    dfs(x+1,cnt);
    room[j][k]=0;//把第x个考生从第j个考场拿出来，回溯
}

如果room[j][k]!=0表示while是通过map[x][room[j][k]]!=0退出的。这说明第j个考场有和第x个考生认识的人，那么我不可以把第x个考生放在第j个考场。

最后我还要考虑新开辟一个考场的情况，因为可能我当前已有的考场都有与第x个考生认识的人，这个时候我不得不开辟一个新考场。但是即便上述情况不会发生，我依然要开辟一个新考场。因为dfs就是要把所有可能的情况都遍历一遍，当然，如果你确定它不会是合法答案，是可以剪枝的。

//当所有房间都有认识的人时新增加一个房间,这种可能每次dfs都要包含
//以穷尽所有可能
room[j][1]=x;
dfs(x+1,cnt+1);
room[j][1] = 0;//回溯

题目代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;
public class Main{
    static int n;
    static int[][] map;
    static int[][] room;
    static int min = 110;
public static void main(String[] args) throws IOException {
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    st.nextToken();
    n = (int)st.nval;
    st.nextToken();
    int m = (int)st.nval;
    map = new int[n+1][n+1];
    room = new int[n+1][n+1];//目前第i个考场第j个人的编号
    for (int i = 0; i < m; i++) {
        st.nextToken();
        int a = (int)st.nval;
        st.nextToken();
        int b = (int)st.nval;
        map[a][b] = 1;
        map[b][a] = 1;
    }
    dfs(1,1);
    System.out.println(min);
}
static void dfs(int x, int cnt){//x 代表当前第x个人,cnt代表当前已经使用的考场数
    if(cnt>=min) return;
    if(x==n+1){
        min = Math.min(min,cnt);
        return;
    }
    int j,k;
    for(j=1; j<=cnt; j++){
        k=1;
        while(room[j][k]!=0 && map[x][room[j][k]]==0){
            k++;
        }
        if(room[j][k]==0){
            room[j][k]=x;
            dfs(x+1,cnt);
            room[j][k]=0;//回溯
        }
    }//当所有房间都有认识的人时新增加一个房间,这种可能每次dfs都要包含
    //以穷尽所有可能
    room[j][1]=x;
    dfs(x+1,cnt+1);
    room[j][1] = 0;//回溯
}
}

开心

题目分析

基本思路：

对于这道题我们要遍历的是在哪一个位置上填“+”。那么我们可以定义一个数组vis[i]，如果它为真表示我们在数字从左向右数第i个数字和第i+1个数字之间添加一个“+”。最后我们要判断所有的“+”是否都被用完了。

细节梳理：

因为我要遍历数字每一位上的值，所以在存数字的时候，我直接用字符数组存，这样取每一位上的值时比较方便。

Scanner sc = new Scanner(System.in);
n = sc.next();
k = sc.nextInt();
arr = n.toCharArray();
vis = new boolean[arr.length];

注意假设数字的长度为n，那么“+”不能放在位置n，因为我们要保证“+”的右边有数字，所以vis数组的结束位置应该是比n小1的地方。下面代码的end表示vis数组的结束位置。举个例子，比如1234，长度为4，我顶多在123的右边放个“+”变成123+4，即vis[2]=true，注意数组下标是从0开始的，当i遍历到3也就是vis.length - 1时，说明我该考虑的位置都考虑完了，接下来应该是求此方案下得到的数的值，所以end是结束位置。

 end = vis.length - 1; //vis能插入+的有效范围 n.length - 1

接下来我们考虑在某个位置上插入“+”。如下代码，这里是stp表示当前遍历到的位置下标，ki表示当前还剩下的可以插入的“+”数量。那么对于当前位置stp来说我可以选择插入“+”，也可以不插入“+”，当i=1时表示我选择的是插入，那么这里要注意，能插入的前提是我还有“+”可以使用，所以要判断ki是否大于0。要插入的话就把vis[stp]置为true。然后进入下一个位置的dfs，如果vis[stp]为true表示我插入了，那么“+”的数量ki就要-1.dfs结束之后，我要做下一个选择了，那么我要把之前选择记录的值复原，也就是把vis[stp]变为false。

static void DFS(int stp, int ki) {
    ......
    for (int i = 0; i < 2; ++i) { //0不插入+，1插入+
        vis[stp] = i == 1 && ki > 0;
        DFS(stp + 1, vis[stp] ? ki - 1 : ki);
        if (vis[stp]) vis[stp] = false;
    }
}

接下来，如果我把所有位置都判断完了是否添加“+”时，我要求当前情况下得到的值。

static void DFS(int stp, int ki) {
        if (stp == end) {//遍历到了终点
            if (ki == 0) { //当使用“+”都用完了才合法
                long sum = 0;
                long ans = 0;
                for (int i = 0; i < arr.length; ++i) {
                    ans = ans * 10 + (arr[i] - '0');
                    if (vis[i]) {//如果出现了“+”，则加上之前的数字，然后ans重置为0.
                        sum += ans;
                        ans = 0;
                    }
                }
                sum += ans; //加上最后一个数字
                if (sum < min) min = sum;//记录最小值
                if (sum > max) max = sum;//记录最大值
            }
            return;
        }
       .....
    }

上述过程举个例子。假设原始数字是1234，k=1，那么vis[1]=true

i=0 ans=1;i=1 ans=12 sum=sum+ans=12 ans=0;i=2 ans=3;i=3 ans=34;for循环结束，但是最后的34我没有加上，我要加上，所以有sum+=ans=sum+34=12+34=46

题目代码

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main{
    
    static String n;
    static int k, end;
    static char[] arr;
    static boolean[] vis;
    static long min = Long.MAX_VALUE, max = 1;
    static HashSet<String> set = new HashSet<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.next();
        k = sc.nextInt();
        arr = n.toCharArray();
        vis = new boolean[arr.length];
        end = vis.length - 1; //vis能插入+的有效范围 n.length - 1
        sc.close();
        if (n.length() > 1) {
            DFS(0, k);
            System.out.println(max - min);
        } else {
            System.out.println(0);
        }
    }
    
    static void DFS(int stp, int ki) {
        if (stp == end) {
            if (ki == 0) { //当使用完全才合法
                long sum = 0;
                long ans = 0;
                for (int i = 0; i < arr.length; ++i) {
                    ans = ans * 10 + (arr[i] - '0');
                    if (vis[i]) {
                        sum += ans;
                        ans = 0;
                    }
                }
                sum += ans; //加上最后一段
                if (sum < min) min = sum;
                if (sum > max) max = sum;
            }
            return;
        }
        for (int i = 0; i < 2; ++i) { //0不插入+，1插入+
            vis[stp] = i == 1 && ki > 0;
            DFS(stp + 1, vis[stp] ? ki - 1 : ki);
            if (vis[stp]) vis[stp] = false;
        }
    }

}

买瓜

题目分析

题目代码

DFS进阶2——剪枝

BFS

BFS基础——图的遍历

迷宫(bfs)

题目分析

迷宫最短路问题最简单的做法就是使用bfs去做，bfs与dfs的区别是bfs第一次走到终点的路径一定是最短路，他不用把所有可行路径都遍历一次。接下来大致讲一下bfs的过程。

在bfs的过程我是同时多个方向扩展路径，所以每一个点，当前我走到这里需要的步数以及这条路上的方向我都要记录，所以我要自己写一个节点类，里面存了节点坐标和走到该点的一个路径，这个路径既表示了这条路上每一步走的方向也表明了路的长度。x和y表示当前点的坐标，pathString表示走到当前点的路径。

static class node{
    int x;
    int y;
    String pathString;
    public node(int x, int y, String pathString) {
        super();
        this.x = x;
        this.y = y;
        this.pathString = pathString;
    }

}

首先把起点加入队列，并标记起点已经被访问过，

LinkedList<node> queue = new LinkedList<>();//申请一个队列
queue.add(new node(0, 0, ""));//把起点放入队列
visit[0][0] =1;
String shunxv ="";//记录最短路径

然后依次从队列里面取出点，直到队列为空。取出点后我们先判断该点是否为终点节点，如果是说明我们找到了一条最短路，后续不需要遍历了，直接退出。否则我要向四个方向去遍历。通过if语句判断下一个位置的坐标是否越界，下一个位置是否可走，下一个位置是否已经被遍历过，都满足的话我就可以走向下一个位置，把它对应的信息添加到队列里面，然后标记该位置已经被走过。

while(!queue.isEmpty()){
    node  t = queue.poll();
    int x1 = t.x;
    int y1 = t.y;
    String str1 = t.pathString;
    if(x1==n-1&&y1==m-1){//判断是否走到终点
        shunxv = str1;
        break;
    }
    for(int i=0;i<4;i++){//向四个方向去遍历
        int x2= x1+nextx[i];
        int y2= y1+nexty[i];
        if(x2>=0&&x2<=n-1&&y2>=0&&y2<=m-1&&map[x2][y2]=='0'&&visit[x2][y2]!=1){
            queue.add(new node(x2, y2, str1+direct[i]));
            visit[x2][y2]=1;
        }
    }
}

题目代码

import java.util.LinkedList;
import java.util.Scanner;
public class Main{
	/*
	 * 在步数最少的前提下，请找出字典序最小的一个作为答案
	 * 如何保证找到的第一个路径一定是字典序最小的
	 * 遍历的时候，按照字典序从小到大的顺序去遍历
	 * D<L<R<U
	 * DDRURRDDDR
	 * DRRURRDDDR
	 * 如何记录我们的路径
	 * bfs 
	 * node{
	 * x，y，path//走到当前节点的路径
	 * }
	 * path
	 */
	static class node{
		int x;
		int y;
		String pathString;
		public node(int x, int y, String pathString) {
			super();
			this.x = x;
			this.y = y;
			this.pathString = pathString;
		}
		
	}
    static int n = 30;
    static int m = 50;
    static char[][]  map = new char[n][m];
    static char[] direct = {'D','L','R','U'};
    static int[] nexty = {0,-1,1,0};
    static int[] nextx = {1,0,0,-1};
    static int[][] visit = new int[n][m];
    static String res;
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	shuju();
    sc.close();
	bfs();
}
private static void shuju() {
	// TODO Auto-generated method stub
	String string = "01010101001011001001010110010110100100001000101010"
			+"00001000100000101010010000100000001001100110100101"
			+"01111011010010001000001101001011100011000000010000"
			+"01000000001010100011010000101000001010101011001011"
			+"00011111000000101000010010100010100000101100000000"
			+"11001000110101000010101100011010011010101011110111"
			+"00011011010101001001001010000001000101001110000000"
			+"10100000101000100110101010111110011000010000111010"
			+"00111000001010100001100010000001000101001100001001"
			+"11000110100001110010001001010101010101010001101000"
			+"00010000100100000101001010101110100010101010000101"
			+"11100100101001001000010000010101010100100100010100"
			+"00000010000000101011001111010001100000101010100011"
			+"10101010011100001000011000010110011110110100001000"
			+"10101010100001101010100101000010100000111011101001"
			+"10000000101100010000101100101101001011100000000100"    //D -> L -> R -> U
			+"10101001000000010100100001000100000100011110101001"
			+"00101001010101101001010100011010101101110000110101"
			+"11001010000100001100000010100101000001000111000010"
			+"00001000110000110101101000000100101001001000011101"
			+"10100101000101000000001110110010110101101010100001"
			+"00101000010000110101010000100010001001000100010101"
			+"10100001000110010001000010101001010101011111010010"
			+"00000100101000000110010100101001000001000000000010"
			+"11010000001001110111001001000011101001011011101000"
			+"00000110100010001000100000001000011101000000110011"
			+"10101000101000100010001111100010101001010000001000"
			+"10000010100101001010110000000100101010001011101000"
			+"00111100001000010000000110111000000001000000001011"
			+"10000001100111010111010001000110111010101101111000";
			
			//将上面的一大串字符转为数组中存储，且数组为int型，仅存0 和 1两个值 
			int[][] moze= new int[30][50];
			for (int i = 0 ; i < 30 ; i++) {
				for(int j = 0 ; j < 50 ; j++) {
					map[i][j] = string.charAt(i*50+j); //
				}
			}
}
private static void bfs() {
	// TODO Auto-generated method stub
	LinkedList<node> queue = new LinkedList<>();//申请一个队列
    queue.add(new node(0, 0, ""));//把起点放入队列
    visit[0][0] =1;
    String shunxv ="";//记录最短路径
    while(!queue.isEmpty()){
        node  t = queue.poll();
        int x1 = t.x;
        int y1 = t.y;
        String str1 = t.pathString;
        if(x1==n-1&&y1==m-1){//判断是否走到终点
            shunxv = str1;
            break;
        }
        for(int i=0;i<4;i++){//向四个方向去遍历
            int x2= x1+nextx[i];
            int y2= y1+nexty[i];
            if(x2>=0&&x2<=n-1&&y2>=0&&y2<=m-1&&map[x2][y2]=='0'&&visit[x2][y2]!=1){
                queue.add(new node(x2, y2, str1+direct[i]));
                visit[x2][y2]=1;
            }
        }
    }
    System.out.println(shunxv);
}
}

大胖子走迷宫

题目分析

这个是迷宫题的拓展，本质还是一样的。那么不同之处在于这个人占的面积。一开始他是5*5的大小，在正常情况下，我判断一个人可不可以走向下一个格子，我只需要判断下一个格子能不能走即可，但是现在这种情况，我需要判断5*5的格子能不能走。那么也就是下一个要走的格子以及它的上下左右两步内的邻居都要判断，即

(x-2,y-2)	(x-2,y-1)	(x-2,y)	(x-2,y+1)	(x-2,y+2)
(x-1,y-2)	(x-1,y-1)	(x-1,y)	(x-1,y+1)	(x-1,y+2)
(x,y-2)	(x,y-1)	中心点(x,y)	(x,y+1)	(x,y+2)
(x+1,y-2)	(x+1,y-1)	(x+1,y)	(x+1,y+1)	(x+1,y+2)
(x+2,y-2)	(x+2,y-1)	(x+2,y)	(x+2,y+1)	(x+2,y+2)

通过上述表格可以看出我们整个要判断的范围其实是从(x-2，y-2)到(x+2，y+2)。

下一阶段，经过了t时刻，它的体积会变成3*3的大小，此时我们要判断的其实就是下一个要走的格子以及它的上下左右一步内的邻居都要判断，即

(x-1,y-1)	(x-1,y)	(x-1,y+1)
(x,y-1)	中心点(x,y)	(x,y+1)
(x+1,y-1)	(x+1,y)	(x+1,y+1)

通过上述表格可以看出我们整个要判断的范围其实是从(x-1，y-1)到(x+1，y+1)。

再下一阶段，经过了2t时刻，它的体积会变成1*1的大小，就是正常大小。那么判断范围就变成了(x-0，y-0)到(x+0，y+0)，其实就是只判断(x,y)。

通过上述分析我们可以发现，范围的那个变量就是x和y加或者减去的那个值从2变成了1，又从1变成了0.那么我们可以用一个变量来表示它，即nr。nr=2时表示我此时的体积是5*5，nr=1时表示我此时的体积是3*3，nr=0时表示我此时的体积是1*1。bfs代码如下

取出队中的节点，首先判断我是否到达了终点，到达了就打印答案，然后退出。

private static void bfs() {
	while(queue.size()!=0) {
		Node node = queue.poll();
		int x = node.x;
		int y = node.y;
		int t = node.t;
		if(x == n-3 &&y== n-3) {
			System.out.println(t);
			return;
		}

注意我们题目中说了，我可以原地不动，所以我要把这种走法考虑进去，而我原地不动的目的其实是为了消耗脂肪，变成比原来更小的体积，如果我体积已经是1*1了那么我没必要做这个操作，所以我有一个判断，t是走到这一步过去的时间，如果它大于等于k的2倍其实就是说明他已经变成了1*1，所以只有t < 2*k时，才进行该操作。

//这个if语句是干什么的  停留在原地不动  是为了消耗脂肪 变小
if(t / k < 2) {
    queue.add(new Node(x, y, t+1));
}

接下来就是向四个方向遍历，这里和普通版本的思路一致，稍微复杂点的地方是我要判断很多个格子是否都可以走。这里变量nr的作用在前面解释过了，如果当前的时间大于等于2*k，那么nr=0，如果当前的时间大于等于k，那么nr=1，否则nr=2。当然，在遍历的时候我们是从(nx-nr,ny-nr)遍历到(nx+nr,ny+nr)，那么我们要注意是否会越界。

for (int i = 0; i < 4; i++) {
    int nx = x + d[i][0];
    int ny = y + d[i][1];
    int nr;
    if(t>=2*k) nr = 0;
    else if(t>=k) nr = 1;
    else nr = 2;
    if(nx-nr<0 || nx+nr>=n || ny-nr<0 || ny+nr>=n||visit[nx][ny]==1) {
        continue;
    }
    boolean ok = true;//记录5*5或者3*3或者1*1的格子里是否有障碍物
    //与迷宫的不同之处就在于 判断障碍物的时候不知判断nx,ny位置
    for (int j = nx-nr; j <= nx+nr; j++) {
        for (int k = ny-nr; k <= ny+nr; k++) {
            if(map[j][k] == '*') {
                ok = false;
                break;
            }
        }
    }

最后，遍历完了都可以走，那么就走向下一个节点，并且将下一个节点入队，

if(ok) {
    visit[nx][ny] = 1;
    queue.add(new Node(nx, ny, t+1));
}

题目代码

import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
public class Main{
	/*
	 * 小明的体积在走迷宫的过程中有什么影响。
	 */
	static int flag=0;
	static int[][] visit;
	static int[][]  d = {{0,1},{0,-1},{1,0},{-1,0}};
	static char[][] map; 
	static int[] r = {2,1,0};
	static Queue<Node> queue = new LinkedList<Node>();
	static int n;
	static int k;
	static class Node{
		int x;
		int y;
		int t;
		public Node(int x, int y, int t) {
			super();
			this.x = x;
			this.y = y;
			this.t = t;
		}		
	}
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	n = scanner.nextInt();
	k = scanner.nextInt();
	map = new char[n][n];
	visit = new int[n][n];
	for (int i = 0; i < map.length; i++) {
		map[i] = (scanner.next()).toCharArray();
	}
	queue.add(new Node(2, 2, 0));
	visit[2][2]=1;
	bfs();
	System.out.println();
}
private static void bfs() {
	while(queue.size()!=0) {
		Node node = queue.poll();
		int x = node.x;
		int y = node.y;
		int t = node.t;
		if(x == n-3 &&y== n-3) {
			System.out.println(t);
			return;
		}
		//这个if语句是干什么的  停留在原地不动  是为了消耗脂肪 变小
		if(t / k < 2) {
			queue.add(new Node(x, y, t+1));
		}		
		for (int i = 0; i < 4; i++) {
			int nx = x + d[i][0];
			int ny = y + d[i][1];
			int nr = (t / k) > 2 ? 0 : r[t/k];//根据t和k的关系获取nr的大小
			if(nx-nr<0 || nx+nr>=n || ny-nr<0 || ny+nr>=n||visit[nx][ny]==1) {
				continue;
			}
			boolean ok = true;//记录5*5或者3*3或者1*1的格子里是否有障碍物
			//与迷宫的不同之处就在于 判断障碍物的时候不知判断nx,ny位置
			for (int j = nx-nr; j <= nx+nr; j++) {
				for (int k = ny-nr; k <= ny+nr; k++) {
					if(map[j][k] == '*') {
						ok = false;
						break;
					}
				}
			}
			if(ok) {
				visit[nx][ny] = 1;
				queue.add(new Node(nx, ny, t+1));
			}
		}
	}
}
}