1查找出岛屿的数量
这一题需要思考在使用递归时是使用广度遍历还是深度遍历！我觉得这一题是在找的时候，是需要将所有的为1的值都要变成0，只要连起来都需要变成水。所以可以想象为从一个点出发，需要找到这个点周围所有的1，所以使用广度优先搜索！
class Solution {
public int numIslands(char[][] grid) {
//记录下当前岛屿的数量
int m=grid.length;
int n=grid[0].length;
int result=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
//说明是一个岛屿，需要进行 计数，然后将此岛屿周围为1的值都变成0；
if(grid[i][j]=='1'){
result++;
solution(grid,i,j);
}
}
}
return result;
}
public void solution(char[][] map , int i,int j){
//如果当前岛屿已经越界，或者直接为0，则可以直接返回
if(i<0||i>=map.length||j<0||j>=map[0].length||map[i][j]=='0'){
return ;
}
//走到此处，说明当前是一个岛屿，需要将该岛屿变成0
map[i][j]='0';
//然后向四个方向找岛屿，这里使用了广度优先搜索啊
solution(map,i+1,j);
solution(map,i-1,j);
solution(map,i,j+1);
solution(map,i,j-1);
}
}
2迷宫只有一条路，并且一次走一步的问题输出路径(只有一条路径使用深度优先算法)
注意和第一题的区别！这题只是说找到一条路径即可，所以应该采用深度优先搜索的方式，当走不通之后，在进行回溯。
import java.util.*;
// 题目已经提示了 【迷宫只有一条通道】，则直接使用 DFS 找路径就行了，如有多条路径找最短考虑使用 BFS
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int rows=in.nextInt();
int clos=in.nextInt();
int[][] map = new int[rows][clos];
for(int i=0;i<rows;i++){
for(int j=0;j<clos;j++){
map[i][j]=in.nextInt();
}
}
List<Node> path= new ArrayList<>();
backTracking(map,0,0,path);
for(Node node: path){
System.out.println("("+node.x+","+node.y+")");
}
}
//使用深度优先搜索解决问题！
public static boolean backTracking(int[][] map,int x,int y,List<Node> path){
//怎么进行深度优先搜索进行查找呢？
if(x==map.length-1&&y==map[0].length-1){
path.add(new Node(x,y));
return true;
}
//当前节点越界或者遇到墙，都不可以走
if(x<0||x>map.length-1||y<0||y>map[0].length-1||map[x][y]==1){
return false;
}
//当前节点可以继续走，所以需要将当前节点加入到路径中，并且置为已经走过
path.add(new Node(x,y));
map[x][y]=1;
if(backTracking(map,x-1,y,path)){
return true;
}
//向下走的通就向下走
if(backTracking(map,x+1,y,path)){
return true;
}
if(backTracking(map,x,y+1,path)){
return true;
}
if(backTracking(map,x,y-1,path)){
return true;
}
//此时都走不通，就直接返回,并且将走过的路置会去
map[x][y]=0;
path.remove(path.size()-1);
return false;
}
}
class Node{
int x;
int y;
public Node(int x,int y){
this.x=x;
this.y=y;
}
}
3迷宫有多条路径，每次走一步，问最短的路径(因为有多条路径，所以需要广度优先搜索)
import java.util.*;
public class Main {
public static ArrayList<int[]> path = new ArrayList<>();//搜索所有可能的路径
public static ArrayList<int[]> best_path = new ArrayList<>();//最短路径
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
path.clear();
best_path.clear();//每个用例之前，都要清空下路径
int n = in.nextInt();
int m = in.nextInt();
int[][] maze = new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
maze[i][j] = in.nextInt();
}
}
dfs(0,0,maze);//深搜+回溯
for(int[] pathi:best_path){
System.out.println("(" + pathi[0] + "," + pathi[1] + ")");
}
}
}
public static void dfs(int i,int j,int[][] maze){
//越界了
if(i<0 || i>maze.length-1 || j<0 || j>maze[0].length-1){
return;
}
//撞墙了
if(maze[i][j]==1){
return;
}
//终止条件,找到终点了
if(i==maze.length-1 && j==maze[0].length-1){
path.add(new int[]{maze.length-1,maze[0].length-1});//添加终点
if(best_path.size()==0 || path.size()<best_path.size()){//遇到更短的路径
best_path.clear();//清空之前的路径
for(int[] path0:path){
best_path.add(path0);
}
}
return;
}
maze[i][j] = 1;//标记走过的点
path.add(new int[]{i,j});//添加到路径中
dfs(i-1,j,maze);
dfs(i+1,j,maze);
dfs(i,j-1,maze);
dfs(i,j+1,maze);//以i j为中心，上下左右搜索
maze[i][j] = 0;//回溯，恢复到之前的状态
path.remove(path.size()-1);//回溯，移除最后一个点
}
}
3迷宫有多条路径，每次最多走k步，问最少几步能走到？
（需要学习，暂时还没有解决，有好的解决办法记得踢我一脚。。。）
