深搜与广搜
深度优先搜索DFS理论
递归三部曲+回溯三部曲+深搜三部曲 模板都是一样的
1.确认递归函数的返回值类型和参数
void dfs(图，目前搜索的节点)
一般情况下，深搜需要 路径集合 保存所有路径，需要单一路径。路径集合 和 单一路径 可以放在全局变量中。
传入参数有三个，一个是图，用来遍历的；一个是目前我们遍历的节点，定位为x；最后一个为保存的终点n，当遍历的时候，用来判断当 x==n 的时候，找到了终点。
所以综上，初始代码应该是这样的：
List<List<Integer>> graph; //收集符合条件的路径
List<Integer> path; //初始节点到终点的路径
//x：目前遍历的节点
//graph：存当前的图
//n：终点
void dfs(int[][] graph, int x, int n){}2.确认终止条件
if(终止条件){
存放结果;
return;
}
3.处理目前搜索节点出发的路径
for(选择：本节点所连接的其它节点){
处理节点;
dfs(图，选择的节点);//递归
回溯，撤销处理结果
}
整体代码框架如下：
int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};// 表示四个方向
// grid 是地图，用二维数组存储
// visited 标记 访问过的 节点，，不要重复访问
// x,y表示开始搜索节点的下标
void bfs(in[][] grid, boolean[][] visited, int x, int y){
//遍历当前节点的四个方向
for(int i = 0; i < 4; i++){
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
// 坐标越界了 直接跳过
if(nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length){
continue;
}
// 如果节点没被访问过
// 具体处理逻辑 判定
if(!visited[nextX][nextY]){
visited[nextX][nextY] = true;// 表明当前节点已经被访问过，标记为true，避免重复访问
bfs(grid, visited, nextX, nextY); // 开始递归，遍历下一层
}
}
}98.所有可达路径
图的存储方式：邻接表和邻接矩阵
邻接矩阵如何构建？
邻接矩阵使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
本题有n个节点，因为节点标号是从1开始的，为了节点标号和下标对齐，我们申请（n+1）*（n+1）的二维数组。
int[][] graph = new int[n+1][n+1];
输入m个边，构造方式如下：
for(int i = 0; i < m; i++){
int s = scanner.nextInt();
int t = scanner.nextInt();
//使用邻接矩阵，1 表示 节点 s 指向 节点 t
graph[s][t] == 1;
}
深度优先搜索
深度优先搜索三部曲
1.确认递归函数，参数
传入参数有三个，一个是图，用来遍历的；一个是目前我们遍历的节点，定位为x；最后一个为保存的终点n，当遍历的时候，用来判断当 x==n 的时候，找到了终点。
所以综上，初始代码应该是这样的：
List<List<Integer>> graph = new ArrayList<>(); //收集符合条件的路径
List<Integer> path = new ArrayList<>(); //初始节点到终点的路径
//x：目前遍历的节点
//graph：存当前的图
//n：终点
void dfs(int[][] graph, int x, int n){
}
2.确定终止条件
当目前遍历的节点 为 最后一个节点n 的时候，就找到了 一条从出发点到终止点的 路径
if(x == n){
result.add(new ArrayList<>(path));
return;
}
3.处理目前搜索节点出发的路径
接下来是走 当前遍历节点 x 的下一个节点
首先要找到 x节点 都 指向了 哪些节点？遍历方式如下：
for(int i = 1; i <= n; i++){//遍历节点x链接的所有节点
if(graph[x][i] == 1){//说明 x 指向的节点 就是i
后续操作
}
}
接下来就是 将选中x所指向的节点，加入到单一路径来
path.add(i);
进入下一层递归
dfs(graph, i, b);
回溯，撤销本次添加节点的操作
path.remove(path.size()-1);
综上第3步整合代码如下：
for(int i = 1; i <= n; i++){//遍历节点x链接的所有节点
if(graph[x][i] == 1){//说明 x 指向的节点 就是i
path.add(i);//将选中x所指向的节点，加入到单一路径来
dfs(graph, i, b);//进入下一层递归
path.remove(path.size()-1);//回溯，撤销本次添加节点的操作
}
}
打印结果
以上代码中，结果都存在result集合中，集合中的每个元素 又都是一个集合，将所有路径打印出来
本题要求路径打印的时候要求：每个元素间都有空格，最后一个元素没有空格
if(result.size() == 0){
System.out.print(-1);
}
for(List<Integer> pa : result){
for(int i = 0; i < pa.size() – 1; i++){
System.out.print(pa.get(i) + ” “);
}
System.out.println(pa.get(pa.size() – 1));
}
完整ACM代码如下：
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main{
static List <List<Integer>> result = new ArrayList<>();
static List <Integer> path = new ArrayList<>();
//1.确定返回值类型和传入参数
public static void dfs(int[][] graph, int x, int n){
//2.确定终止条件
if(x == n){
result.add(new ArrayList<>(path));
return;
}
for(int i = 1; i <= n; i++){
if(graph[x][i] == 1){
path.add(i);
dfs(graph, i, n);
path.remove(path.size()-1);
}
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();//N个节点
int M = scanner.nextInt();//M条边
//创建 邻接矩阵
int[][] graph = new int[N+1][N+1];
//初始化 邻接矩阵
while(M > 0){
M--;
int s = scanner.nextInt();
int t = scanner.nextInt();
graph[s][t] = 1;
}
path.add(1);
dfs(graph, 1, N);
//输出结果
if(result.isEmpty()){
System.out.print(-1); }
for(List<Integer> pa : result){
for(int i = 0; i < pa.size() - 1; i++){
System.out.print(pa.get(i) + " ");
}
System.out.println(pa.get(pa.size()-1));
}
}
}图的存储方式：邻接表如何构建？
邻接表 使用 数组 + 链表 的方式来表示。邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。
//节点编号从1到n，所以申请 n+1 的数组
List<LinkedList<Integer>> graph = new ArrayList<>(n+1);
//相比较 邻接矩阵初始化(数组默认值为0)， 邻接表 需要遍历每个 元素 添加新的 LinkedList 集合
for(int i = 0; i < = n; i++){
graph.add(new LinkedList<>());
}
//初始化邻接表
for(int i = 0; i < m; i++){
int s = scanner.nextInt();
int t = scanner.nextInt();
graph.get(s).add(t);
}
深搜三部曲 与 邻接矩阵 的思路一样
这里唯一不同就是 处理逻辑上 我们需要找到当前遍历节点x 的 所有链接的节点
在邻接矩阵中，我们通过从1到n遍历 然后判断 graph[x][i] == 1 来判定 是否有链接
而在邻接表中，我们需要遍历 当前节点x 后面 的 所有链表元素， 这些链表元素 就是 它 有链接的 点
因此代码如下：
for(int i : graph.get(x)){// 找到 x 指向的节点
path.add(i);// 遍历到节点加入到路径中来
dfs(graph, i, n);// 递归
path.remove(path.seiz() – 1);// 回溯
}
广度优先搜索BFS理论
一圈一圈搜索的模拟是如何实现的？
使用队列或者栈都可以，但是队列是常用的。
BFS一圈一圈的遍历方式，一旦遇到终止点，那么就一定是一条最短路径。
遍历每个节点的所有链接的点，链接的点再继续遍历其所有链接的点，层层遍历，直到终止点，完成广度优先搜索。
模板设置
int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};// 表示四个方向
// grid 是地图，用二维数组存储
// visited 标记 访问过的 节点，，不要重复访问
// x,y表示开始搜索节点的下标
void bfs(in[][] grid, boolean[][] visited, int x, int y){
//遍历当前节点的四个方向
for(int i = 0; i < 4; i++){ int nextX = x + dir[i][0];
Int nextY = y + dir[i][1];
// 坐标越界了 直接跳过
if(nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length){
continue;
}
// 如果节点没被访问过
// 具体处理逻辑 判定
if(!visited[nextX][nextY]){
visited[nextX][nextY] = true;// 表明当前节点已经被访问过，标记为true，避免重复访问
bfs(grid, visited, nextX, nextY); // 开始递归，遍历下一层
}
}
}
99.岛屿数量
深搜版代码：
1.递归函数的 传入参数
//grid 作为 二维数组 存储的是 地图
// visited 作为 布尔类型的 二维数组，与 grid 数组相对应，grid中的位置对应到visited的位置为true表示已经被访问过，为false 表示未被访问。初始化时 默认值 为 false，表示所有点都没有被访问过，符合我们的预期。
// x，y 传入的 坐标值
Public static void dfs(int[][] grid, boolean[][] visited, int x, int y){
}
2.确定终止条件
分析：当前遍历的节点x,y为负数或者越界，则返回
遍历的当前节点为海水(grid[x][y] == 0) 或者 已经被 访问过(visited[x][y] == true)
注意：要先判断x 和 y 是否越界，然后再判断 当前节点是否为海水还是 已经被访问过
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0 || visited[x][y] == true){
Return;
}
3.处理业务逻辑
进入逻辑意味着该节点已经被访问过，立刻将其进行标记
开始遍历该节点所有链接的上下左右四个方向的节点
visited[x][y] = true;
for(int i = 0; i < 4; i++){
Int nextX = x + dir[i][0];
Int nextY = y + dir[i][1];
// 直接进入递归
dfs(grid, visited, nextX, nextY);
}
广搜版代码：
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
//grid 是 地图， 二维数组
// visited 标记访问过的节点，不能重复访问
// x,y 表示 开始 搜索节点的 下标
public static void bfs(int[][] grid, boolean[][] vsisted, int x, int y){
// 定义 队列，队列 中 的每个元素 是 大小为2的一维数组
Deque<int[]> queue = new ArrayDeque<>();
// 起始节点 加入 队列
queue.offer(new int[]{x, y});
// 只要加入队列，立刻标记为访问过的节点
vsisted[x][y] = true;
// 开始遍历队列的元素
while(!queue.isEmpty()){
// 从 队列 中取出元素
int[] current = queue.poll();
// 当前节点 坐标
int x1 = current[0];
int y1 = current[1];
// 开始 向 当前节点 的 四个方向 左右上下 去遍历
for(int i = 0; i < 4; i++){
int x2 = x1 + dir[i][0];
int y2 = y1 + dir[i][1];
if(x2 < 0 || x2 >= grid.length || y2 < 0 || y2 >= grid[0].length){
continue;
}
// 如果节点没被访问过 且 该节点为 陆地
if(vsisted[x2][y2] == false && grid[x2][y2] == 1){
// 队列 添加该节点为 下一轮 要遍历的 节点
queue.offer(new int[]{x2, y2});
// 只要 加入队列 立刻 标记，避免重复访问
vsisted[x2][y2] = true;
}
}
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
//初始化
int[][] grid = new int[n][m];
boolean[][] visited = new boolean[n][m];
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
for(int i = 0; i <n; i++){
for(int j = 0; j < m; j++){
if(visited[i][j] == false && grid[i][j] == 1){
ans++;
bfs(grid, visited, i, j);
}
}
}
System.out.print(ans);
}
}
100.岛屿的最大面积
在主函数中遍历每个节点，通过深度优先搜索 来 计算 每个 岛屿 的面积 是多少，然后取最大值
注意点有两个：
1.递归函数dfs的终止条件中，必须先判断当前节点x和y是否越界 然后 再判断 该节点 是否为海水 还是 已经被访问过。
2.主函数每次遍历节点进行dfs深搜之前，都要将陆地的计算面积赋值为0，不然会出现累加的现象。
代码：
import java.util.Scanner;
//深搜
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static int count = 0;
public static int result = 0;
public static void dfs(int[][] grid, boolean[][] visited, int x, int y){
//确定终止条件
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y] == true || grid[x][y] == 0){
return; }
visited[x][y] = true;
count++;
//遍历当前节点的四个方向
for(int i = 0; i < 4; i++){
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
dfs(grid, visited, nextX, nextY);
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
boolean[][] visited = new boolean[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = scanner.nextInt();
}
}
//开始遍历 grid 和 visited
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1 && visited[i][j] == false){
count = 0;//每次计算陆地面积之前都要归0
dfs(grid, visited, i, j);
result = Math.max(result, count);
}
}
}
System.out.print(result);
}
}
import java.util.Scanner;
import java.util.Queue;
import java.util.ArrayDeque;
// 广搜
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static int result = 0;
public static int count = 0;
public static void bfs(int[][] grid, boolean[][] visited, int x, int y){
Queue<Node> q = new ArrayDeque<>();
q.add(new Node(x, y));
visited[x][y] = true;
count++;
while(!q.isEmpty()){
Node n = q.remove();
for(int i = 0; i < 4; i++){
int nextX = n.x + dir[i][0];
int nextY = n.y + dir[i][1];
if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length || grid[nextX][nextY] == 0 || visited[nextX][nextY] == true){
continue;
}
q.add(new Node(nextX, nextY));
visited[nextX][nextY] = true;
count++;
}
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1 && visited[i][j] == false){
count = 0;
bfs(grid, visited, i, j);
result = Math.max(result, count);
}
}
}
System.out.print(result);
}
static class Node{
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
}
101.孤岛的总面积
孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
解题思路：本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地，然后 通过 dfs 或者 bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的 陆地 就可以了。
从 左侧边 和 右侧边 开始 向中间遍历
for(int i = 0; i < n; i++){
if(grid[i][0] == 1){
dfs(grid, visited, i, 0);
}
if(grid[i][m-1] == 1){
dfs(grid, visited, i, m-1);
}
}
从 上边 和 下边 向 中间遍历
for(int i = 0; i < m; i++){
if(grid[0][i] == 1){
dfs(grid, visited, 0, i);
}
if(grid[n-1][i] == 1){
dfs(grid, visited, n-1, i);
}
}
完整代码如下：
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
//深搜
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static int count = 0;
public static int result = 0;
public static void dfs(int[][] grid, boolean[][] visited, int x, int y){
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0 || visited[x][y] == true){
return;
}
grid[x][y] = 0;
visited[x][y] = true;
count++;
for(int i = 0; i < 4; i++){
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
dfs(grid, visited, nextX, nextY);
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m];
//只要从周边找到陆地然后 通过 dfs 或者 bfs 将周边靠陆地且相邻的陆地
//都变成海洋，然后再去重新遍历地图 统计此时还剩下的 陆地就可以了
//从左侧边 和 右侧边 向 中间遍历
for(int i = 0; i < n; i++){
if(grid[i][0] == 1){
dfs(grid, visited, i, 0);
}
if(grid[i][m-1] == 1){
dfs(grid, visited, i, m-1);
}
}
//从上边 和 下边 向 中间遍历
for(int i = 0; i < m; i++){
if(grid[0][i] == 1){
dfs(grid, visited, 0, i);
}
if(grid[n-1][i] == 1){
dfs(grid, visited, n-1, i);
}
}
List<Integer> resultList = new ArrayList<>();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1 && visited[i][j] == false){
count = 0;
dfs(grid, visited, i, j);
resultList.add(count);
}
}
}
for(Integer r : resultList){
result += r;
}
System.out.print(result);
}
}
广搜代码
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
//广搜
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static int count = 0;
public static int result = 0;
public static void bfs(int[][] grid, boolean[][] visited, int x, int y){
Deque<Node> q = new ArrayDeque<>();
q.push(new Node(x, y));
grid[x][y] = 0;
visited[x][y] = true;
count++;
while(!q.isEmpty()){
Node n = q.pop();
for(int i = 0; i < 4; i++){
int nextX = n.x + dir[i][0];
int nextY = n.y + dir[i][1];
if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length || grid[nextX][nextY] == 0 || visited[nextX][nextY] == true){
continue;
}
if(grid[nextX][nextY] == 1 && visited[nextX][nextY] == false){
q.push(new Node(nextX, nextY));
grid[nextX][nextY] = 0;
visited[nextX][nextY] = true;
count++;
}
}
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m];
//只要从周边找到陆地然后 通过 dfs 或者 bfs 将周边靠陆地且相邻的陆地
//都变成海洋，然后再去重新遍历地图 统计此时还剩下的 陆地就可以了
//从左侧边 和 右侧边 向 中间遍历
for(int i = 0; i < n; i++){
if(grid[i][0] == 1){
bfs(grid, visited, i, 0);
}
if(grid[i][m-1] == 1){
bfs(grid, visited, i, m-1);
}
}
//从上边 和 下边 向 中间遍历
for(int i = 0; i < m; i++){
if(grid[0][i] == 1){
bfs(grid, visited, 0, i);
}
if(grid[n-1][i] == 1){
bfs(grid, visited, n-1, i);
}
}
List<Integer> resultList = new ArrayList<>();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1 && visited[i][j] == false){
count = 0;
bfs(grid, visited, i, j);
resultList.add(count);
}
}
}
for(Integer r : resultList){
result += r;
}
System.out.print(result);
}
static class Node{
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
}
102.沉没孤岛
解题思路：本题要将所有孤岛由1变成0
先将周边陆地及其相邻单元陆地 都 从 1 变成 2
然后 再遍历grid将 grid的 1 变成 0 ， 2 变成 1
最后打印出grid
import java.util.Scanner;
//深搜
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void dfs(int[][] grid, int x, int y){
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0 || grid[x][y] == 2){
return;
}
//将周边陆地及其相邻单元陆地 都改为 2
grid[x][y] = 2;
for(int i = 0; i < 4; i++){
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
dfs(grid, nextX, nextY);
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = scanner.nextInt();
}
}
//从 左侧边 和 右侧边 向中间遍历
for(int i = 0; i < n; i++){
if(grid[i][0] == 1){
dfs(grid, i, 0);
}
if(grid[i][m-1] == 1){
dfs(grid, i, m-1);
}
}
//从上边 和 下边 向中间遍历
for(int i = 0; i < m; i++){
if(grid[0][i] == 1){
dfs(grid, 0, i);
}
if(grid[n-1][i] == 1){
dfs(grid, n-1, i);
}
}
//开始遍历grid 找到 为1的陆地 变成 0 即可
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1){
grid[i][j] = 0;
}
if(grid[i][j] == 2){
grid[i][j] = 1;
}
System.out.print(grid[i][j] + ” “);
}
System.out.println();
}
}
}
103.水流问题
解题思路：
每遍历一个点，都是重新创建一个属于他的visited，调用dfs，得到该点的visited，然后判断这张visited中是否在第一组边界和第二组边界中都有true，如果都有，就说明该点符合要求。
使用深搜dfs
1.在dfs方法中，将点(x, y) 可流经 的 地方 全部标记为true
2.在isResult方法中 调用 dfs方法，判断点 (x, y) 对应的 visited表是否 流经 第一组边界和第二组边界。通过标记位isFirst和isSecond来判断。
3.在主函数中 遍历 grid 的每一个点，调用isResult函数 看是否符合要求
代码如下：
import java.util.Scanner;
//深搜
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
//利用深搜 将 点 x ,y 可流经的 地方全部标记为 true
public static void dfs(int[][] grid, boolean[][] visited, int x, int y){
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y] == true){
return;
}
visited[x][y] = true;
for(int i = 0; i < 4; i++){
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length || visited[nextX][nextY] == true){
continue;
}
if(grid[nextX][nextY] > grid[x][y]){
continue;
}
dfs(grid, visited, nextX, nextY);
}
}
// 判断 点 x,y 通过 dfs 深搜后 得到的 visited 中是否达到在第一组边界和第二组边界
public static boolean isResult(int[][] grid, int x, int y, int n, int m){
//每个点 都 对应 一张visited
boolean[][] visited = new boolean[n][m];
//调用dfs
dfs(grid, visited, x, y);
//标记为isFirst 和 isSecond 用来判断是否流到第一组边界和第二组边界
boolean isFirst = false;
boolean isSecond = false;
//遍历 第一组边界的左边界
for(int i = 0; i < n; i++){
if(visited[i][0] == true){
isFirst = true;
}
}
//遍历 第一组边界的上边界
for(int j = 0; j < m; j++){
if(visited[0][j] == true){
isFirst = true;
}
}
//遍历 第二组边界 的右边界
for(int i = 0; i < n; i++){
if(visited[i][m-1] == true){
isSecond = true;
}
}
//遍历 第二组边界 的下边界
for(int j = 0; j < m; j++){
if(visited[n-1][j] == true){
isSecond = true;
}
}
if(isFirst == true && isSecond == true){
return true;
}
return false;
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = scanner.nextInt();
}
}
//开始遍历
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(isResult(grid, i, j, n, m) == true){
System.out.println(i + ” ” + j);
}
}
}
}
}
104.建造最大岛屿
解题思路：
本题暴力思想是，遍历地图 尝试 将每一个 0 改成 1，然后去搜索地图中的 最大 岛屿面积。
计算地图的 最大面积： 遍历 地图 + 深搜岛屿，时间复杂度为n*n
每改变一个0 的 方格， 都需要重新计算一个地图的 最大面积，所以 整体时间复杂度为n^4
优化思路：
只用一次深搜 把 每个岛屿 的面积记录下来即可
第一步：第一次遍历地图，得出每个岛屿 的 面积，并做好编号记录。即将对应的陆地1改为对应的mark编号grid[x][y] = mark。可以使用map记录，key 为 岛屿编号，value是岛屿的面积。
第二步：第二次遍历地图，遍历 0 的 方格，将0变成1（海水变成陆地），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起。在相加面积时，将遍历的四个方向点对应的mark存入Set集合中，进行去重，加入判断if(Set.contains(grid[x][y]) || !HashMap.containsKey(grid[x][y]))，如果满足该条件说明该节点的陆地面积不应该加入。遍历所有0之后，就可以得到 选一个 0 变成 1 之后的 最大面积。
完整代码：
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
//深搜
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static int count;
public static int mark;
public static int result;
public static void dfs(int[][] grid, boolean[][] visited, int x, int y){
if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y] == true || grid[x][y] == 0){
return; }
count++;
visited[x][y] = true;
grid[x][y] = mark;
for(int i = 0; i < 4; i++){
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
dfs(grid, visited, nextX, nextY);
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m];
//第一次遍历grid 将 每个陆地 进行编号 统计其面积，存入map
Map<Integer, Integer> numS = new HashMap<>();
mark = 2;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1){
count = 0;
dfs(grid, visited, i, j);
numS.put(mark, count);
//更新最大陆地面积，不将海水改成陆地的情况
result = Math.max(result, count);
mark++;
}
}
}
Set<Integer> isIland = new HashSet<>();
//第二次遍历grid ，遍历到海水就将海水变成陆地，遍历该点的四个方向，
//查看是否存在陆地
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 0){
isIland.clear();
int curCount = 1;
for(int k = 0; k < 4; k++){
int nextX2 = i + dir[k][0];
int nextY2 = j + dir[k][1];
if(nextX2 < 0 || nextX2 >= grid.length || nextY2 < 0 || nextY2 >= grid[0].length) continue;
if(isIland.contains(grid[nextX2][nextY2]) || !numS.containsKey(grid[nextX2][nextY2])){
continue;
}
isIland.add(grid[nextX2][nextY2]);
curCount += numS.get(grid[nextX2][nextY2]);
}
//更新最大陆地面积，将海水改成陆地的情况
result = Math.max(result, curCount);
}
}
}
System.out.print(result);
}
}
110.字符串接龙
思路：无向图+BFS求单源最短路径
本题只需求出最短路径的长度即可，不用找出具体路径
本题要解决两个问题：
图中的线是如何连在一起的
起点和终点的最短路径长度
题目中没有给出点与点之间的连线，而是需要自己去连，条件是字符只差一个。
所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。
然后就是求起点和终点的最短路径长度，这里无向图求最短路径，广搜最为合适，广搜只要搜到了终点，那么就一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。
注意：
本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环
使用set来检查字符串是否出现在字符串集合里更快一些
代码：
import java.util.*;
public class Main{
//广搜
public static int bfs(String beginStr, String endStr, List<String> strList){
int len = 1;//路径最开始从1开始计算，题目计算路径是计算节点的个数
Queue<String> q = new LinkedList<>();
Set<String> strSet = new HashSet<>(strList);//通过Set的构造函数将List集合转成
//Set集合，题目要求转换过程中的中间字符串必须是字典strList中的字符串
//用于存储遍历过的字符串，因为题目要求strList里的每个字符串只能用一次
Set<String> visited = new HashSet<>();
q.add(beginStr);
q.add(null);//用于判断是否进入下一层进行广搜
visited.add(beginStr);
while(!q.isEmpty()){
String node = q.remove();
//判断是否进入下一层广搜
if(node == null){
if(!q.isEmpty()){
len++;
q.add(null);
}
continue;
}
//开始遍历该节点node所有链接的节点
char[] strCharArray = node.toCharArray();
for(int i = 0; i < strCharArray.length; i++){
//暂存 此 字符串，用于后续 没有 路径可走可以回滚
char old = strCharArray[i];
for(char j = ‘a’; j <= ‘z’; j++){
strCharArray[i] = j;
//将字符数组转成字符串
String newWord = new String(strCharArray);
if(strSet.contains(newWord) && !visited.contains(newWord)){
visited.add(newWord);
q.add(newWord);
if(newWord.equals(endStr)){
return len + 1;
}
}
}
//回滚，把字符串复原
strCharArray[i] = old;
}
}
return 0;
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();//按下回车在下一行输入
String beginStr = scanner.next();//输入内容，以空格为分割
String endStr = scanner.next();//输入内容，以空格为分割
scanner.nextLine();//按下回车在下一行输入
List<String> strList = new ArrayList<>();
strList.add(beginStr);
strList.add(endStr);
for(int i = 0; i < n; i++){
strList.add(scanner.nextLine());//每输入一个字符串，按下回车在下一行继续输入
}
int result = bfs(beginStr, endStr, strList);
System.out.print(result);
}
}
105.有向图的完全可达性
本题只需要判断从1号节点为起点，是否可以到达所有其他节点，若能，输出1，否则输出-1
有向图搜索全路径的问题，只能使用dfs或者bfs来解决。
深搜三部曲
1.确定递归函数，传入参数
需要传入地图graph（本题地图graph采用的是链接表实现）
当前遍历的节点key
一个布尔类型的一维数组visited，用来标记节点key开始都走过哪些位置
public static void dfs(List<LinkedList<Integer>> graph, int key, boolean[] visited){
}
2.确定终止条件
如果当前遍历的节点key是被访问过的，那么就结束递归，否则继续递归
if(visited[key] == true){
return; }
3.处理当前遍历的节点所有链接的节点
//遍历该节点所有链接节点之前，先要把该节点标记为已经访问过
visited[key] = true;
//开始遍历链接节点
for(int k : graph.get(key)){
dfs(graph, visited, k);
}
综上，深搜方法dfs代码如下：
public static void dfs(List<LinkedList<Integer>> graph, int key, boolean[] visited){
if(visited[key] == true){
return; }
visited[key] = true;
for(int k : graph.get(key)){
dfs(graph, visited, k);
}
}
在主函数中，创建graph，初始化、赋值；创建visited，然后调用dfs方法，最后判断visited从下标1开始，是否有false就说明遍历不到所有节点，输出-1；如果没有false，说明可以遍历所有节点，输出1。
完整代码如下：
import java.util.*;
//深搜
public class Main{
public static void dfs(List<LinkedList<Integer>> graph, boolean[] visited, int key){
if(visited[key] == true){
return;
}
visited[key] = true;
//遍历当前节点key的所有链接的节点
for(int k : graph.get(key)){
dfs(graph, visited, k);
}
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
//初始化邻接表
for(int i = 0; i <= n; i++){
graph.add(new LinkedList<>());
}
//赋值
for(int i = 0; i < k; i++){
int s = scanner.nextInt();
int t = scanner.nextInt();
graph.get(s).add(t);
}
//初始化默认都是false
boolean[] visited = new boolean[n + 1];
dfs(graph, visited, 1);
int result = 1;
//遍历visited结果
for(int i = 1; i < visited.length; i++){
if(visited[i] == false){
result = -1;
break;
}
}
System.out.print(result);
}
}
106.岛屿的周长
该题用不上BFS或者DFS
该题就是遍历每一个空格，遇到岛屿就计算它的上下左右节点的情况
有边可以算入周长的情况一共有两种
情况一：该陆地节点的上下左右节点是海水，则说明是边
情况二：该陆地节点的上下左右节点越界了，则说明是边
代码如下：
import java.util.*;
public class Main{
public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = scanner.nextInt();
}
}
int cir = 0;
//直接遍历grid
//两种情况有边
//情况一：该节点的上下左右节点是海水，则是边
//情况二：该节点的上下左右节点出界了，则是边
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1){
for(int k = 0; k < 4; k++){
int nextX = i + dir[k][0];
int nextY = j + dir[k][1];
if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length || grid[nextX][nextY] == 0){
cir++;
}
}
}
}
}
System.out.print(cir);
}
}
并查集
并查集理论基础
并查集用来解决连通性问题
连通图 + 强连通图
在无向图中，任何两个节点都是可以到达的，我们称之为连通图；如果有节点不能到达其他节点，则为非连通图。
在有向图中，任何两个节点都是可以到达的，我们称之为强连通图。与无向图中的连通图有些不同，因为强连通图是有向图作为基础的，必须任何两个节点都是可以相互到达的，所以要么两节点是双向连接的，要么整个图成环。
何为解决连通性问题？通俗理解就是判断两个元素是否在同一个集合里。
并查集主要有两个功能：
功能一：将两个(或多个)元素添加到一个集合中；
功能二：判断两个(或多个)元素在不在同一个集合。
先来看功能一如何实现：将两个(或多个)元素添加到一个集合中。
我们将三个元素A，B，C（分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通呢？
只需要用一个一维数组来表示，即：father[A] = B,（表示A指向B），father[B] = C，（表示B指向C），这样一来就表示A与B与C连通了（有向连通图）。
代码如下：
//将节点 v 指向 节点 u 的这条边 加入 并查集
void join(int u, int v){
u = find(u);//找节点u的根节点，并赋值为u
v = find(v);//找节点v的根节点，并赋值为v
if(u == v) return;//如果节点u和节点v的根节点是同一个，则说明在同一个集合中，不用两个节点相连直接返回即可
father[v] = u;//说明两个节点根节点不是一个，那么就把两个节点相连，节点v指向节点u
}
至此，通过join方法实现了功能一。我们可以知道A连通B，因为A是索引下标，根据father[A]的数值就可以知道A连通B。那么怎么知道B连通A呢？
因为我们的目的是实现功能二：判断多个元素是否在同一个集合中，所以知道A连通B就已经足够了。
寻根思路就是A，B，C在同一个根下就是同一个集合。
具体来说：给出A元素，就可以通过father[A] = B,father[B] = C,找到根为C
给出B元素，通过father[B] = C，找到根也为C。说明A和B是在同一个集合中。
代码如下：
//并查集寻根的过程
int find(int u){
if(u == father[u]) return u;//如果根就是自己，直接返回
else return find(father[u]); //如果根不是自己，就根据其父节点不断递归找到根节点
}
如何表示C也在同一个元素里呢？我们需要father[C] = C，即C的根也为C，这样就方便表示A，B，C都在同一个集合中了。
所以father数组初始化的时候要father[i] = i,默认自己指向自己
代码如下：
// 并查集初始化
void init(){
for(int i = 0; i < n; i++){
father[i] = i;
}
}
最后再来看看如何实现功能二：判断两个(或多个)元素在不在同一个集合。
如果通过 find 函数 找到 两个元素属于同一个根的话，那么这两个元素就是同一个集合
代码如下：
// 判断 u 和 v 是否找到同一个根
boolean isSame(int u, int v){
u = find(u);
v = find(v);
return u == v;
}
路径压缩：
在实现find函数的过程中，通过递归的方式，不断获取father数组下标对应的数值，最终找到这个集合的根。如果递归次数非常多会导致效率低。我们的目的只需要知道这些节点在同一个根下就可以，所以除了根节点其他所有节点都挂在根节点下，这样在寻根的时候就很快，只需要一步，由原来的时间复杂度O(logn)降为O(1)。
想要实现这样的效果，需要路径压缩，将非根节点的所有节点直接指向根节点。
只需要在递归的过程中，让 father[u] 接住 递归函数 find(father[u]) 的返回结果。
因为find 函数 向上寻找根节点，father[u]表述 u 的父节点，那么让 father[u] 直接获取 find 函数 返回的根节点，这样就让节点 u 的 父节点 变成 根节点。
代码如下：
//并查集寻根的过程
int find(int u){
return u == father[u] ? u : father[u] = find(father[u]);
}
综上：并查集主要有三个功能：
1.寻找根节点，函数：find(int u)，也就是判断节点u的根节点是哪个；
2.将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点下；
3.判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点。
模板代码总结如下：
// 并查集初始化
void init(){
for(int i = 0; i < n; i++){
father[i] = i;
}
}
//将节点 v 指向 节点 u 的这条边 加入 并查集
void join(int u, int v){
u = find(u);//找节点u的根节点，并赋值为u
v = find(v);//找节点v的根节点，并赋值为v
if(u == v) return;//如果节点u和节点v的根节点是同一个，则说明在同一个集合中，不用两个节点相连直接返回即可
father[v] = u;//说明两个节点根节点不是一个，那么就把两个节点相连，节点v指向节点u
}
//并查集寻根的过程
int find(int u){
return u == father[u] ? u : father[u] = find(father[u]);
}
// 判断 u 和 v 是否找到同一个根
boolean isSame(int u, int v){
u = find(u);
v = find(v);
return u == v;
}
107.寻找存在的路径
通过并查集将图转成树的形式。判断两个节点在不在一个集合(就是判断两个节点是不是拥有同一个根节点)+将两个节点添加到一个集合中(就是将这两个节点都指向同一个根节点)。
代码如下：
import java.util.*;
//并查集
public class Main{
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
DisJoint disJoint = new DisJoint(n);
for(int i = 0; i < m; i++){
int s = scanner.nextInt();
int t = scanner.nextInt();
disJoint.join(s, t);
}
int source = scanner.nextInt();
int destination = scanner.nextInt();
if(disJoint.isSame(source, destination) == true){
System.out.print(1);
}else{
System.out.print(0);
}
}
}
//并查集
class DisJoint{
private int[] father;
public DisJoint(int n){
father = new int[n + 1];
for(int i = 0; i <= n; i++){
father[i] = i;
}
}
public void join(int u, int v){
u = find(u);
v = find(v);
if(u == v){
return;
}
father[v] = u;
}
public int find(int u){
return u == father[u] ? u : (father[u] = find(father[u]));
}
public boolean isSame(int u, int v){
u = find(u);
v = find(v);
return u == v;
}
}
108.冗余连接
解题思路：
从前向后遍历每一条边（优先让前面的边连上），边的两个节点如果不在同一个集合(isSame(u, v) == false)，那就加入集合(join(u, v))（即同一个根节点）。如果边的两个节点已经出现同一个集合中(isSame(u, v) == true)，说明这条边的两个节点已经连在一起了，再加入这条边就一定会成环。
代码如下：
import java.util.*;
//思路 ：如果两个节点 是 都指向同一个根节点(即是在同一个集合中)，那么再将这两个节点
//连起来，就一定构成环
public class Main{
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
DisJoint disJoint = new DisJoint(n);
for(int i = 0; i < n; i++){
int s = scanner.nextInt();
int t = scanner.nextInt();
if(disJoint.isSame(s, t) == false){//说明两节点不在同一个集合
//加入同一个集合
disJoint.join(s, t);
}else{//说明两节点在同一个集合
System.out.print(s + ” ” + t);
}
}
}
}
class DisJoint{
private int[] father;
public DisJoint(int n){
father = new int[n + 1];
for(int i = 0; i <= n; i++){
father[i] = i;
}
}
public void join(int u, int v){
u = find(u);
v = find(v);
if(u == v){
return;
}
father[v] = u;
}
public int find(int u){
return u == father[u] ? u : (father[u] = find(father[u]));
}
public boolean isSame(int u, int v){
u = find(u);
v = find(v);
return u == v;
}
}
109.冗余连接II
有向树：该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都 有且只有 一个父节点，而根节点没有父节点。有向树拥有n个节点和n-1条边。
现在有一个有向图，有向图是在 有向树 中的两个没有直接连接 的 节点 中间添加一条有向边。所以有向图是有 n 个节点 和 n条边组成的。
现在需要返回一条可以删除的边，使得删除这条边之后 该有向图 变成了 一颗 有向树
解题思路：
有向树的性质是：只有根节点入度为0，其他节点入度都为1。
情况一：找到入度为2的点，那么删除一条指向该节点的边即可。
情况二：找到入度为2的点，但是只能删除特定的一条边。
情况三：如果没有入度为2的点，说明 图中 有环了，就和 冗余连接 那道题一样了，删除构成环的边即可。
具体写法步骤：
1、把每条边记录下来，并统计节点入度，这道题只会存在一个入度为2的点。
2、前两种入度为2的情况，一定是删除指向入度为2的节点的两条边其中的一条。如果删了一条，就判断这个图是不是一颗有向树，如果是，那么这条边就是答案；如果不是，就删除另外那条边。同时注意要从后向前遍历，因为如果两条边删哪一条都可以成为有向树，就删最后那一条。
3、第三种情况3，明确没有入度为2的情况下，那么一定有 有向环， 找到构成环 的 边就是要删除的边。
综上 我们 需要构建两个方法：
方法一：isTreeAfterRemoveEdge() 判断删一个边之后是不是有向树：将所有边的两端节点分别加入并查集，遇到要删除的边则跳过；如果遇到即将加入并查集的边的两端节点 本来就在并查集了，则说明构成了环。如果顺利将所有边的两端节点（除了要删除的边）加入了并查集，则说明 删除 该条边 还是一棵有向树。
方法二：getRemoveEdge() 确定图中 一定 有了 有向环，那么要找到需要删除的那条边：将所有边的两端节点分别加入并查集，如果遇到即将加入并查集的边的两端节点本来就在并查集了，说明构成了环。
代码如下：
import java.util.*;
public class Main{
static class Disjoint {
private final int[] father;
public Disjoint(int n) {
father = new int[n + 1];
for (int i = 0; i <= n; i++) {
father[i] = i;
}
}
public void join(int n, int m) {
n = find(n);
m = find(m);
if (n == m) return;
father[n] = m;
}
public int find(int n) {
return father[n] == n ? n : (father[n] = find(father[n]));
}
public boolean isSame(int n, int m) {
return find(n) == find(m);
}
}
static class Edge{
int s;
int t;
public Edge(int s, int t){
this.s = s;
this.t = t;
}
}
static class Node{
int id;
int in;
int out;
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//记录入度为2的节点是哪一个（本题只能有一个入度为2的点）
//装填所有输入的节点以及对应的边信息
List<Edge> edges = new ArrayList<>();
Node[] nodeMap = new Node[n + 1];
for (int i = 1; i <= n; i++) {
nodeMap[i] = new Node();
}
int doubleIn = 0;
for(int i = 0; i < n; i++){
int s = scanner.nextInt();
int t = scanner.nextInt();
nodeMap[t].in++;
if(nodeMap[t].in == 2){
doubleIn = t;
}
edges.add(new Edge(s, t));
}
//开始走三个情况的逻辑
Edge result = null;
if(doubleIn != 0){//说明有入度为2的节点
List<Edge> doubleInEdges = new ArrayList<>();
for(Edge edge : edges){
if(edge.t == doubleIn){
doubleInEdges.add(edge);
}
if(doubleInEdges.size() == 2){
break;
}
}
Edge edge = doubleInEdges.get(1);
if (isTreeAfterRemoveEdge(edges, edge, nodeMap)) {
result = edge;
} else {
result = doubleInEdges.get(0);
}
}else{//说明没有入度为2的节点
result = getRemoveEdge(edges, nodeMap);
}
System.out.println(result.s + ” ” + result.t);
}
public static boolean isTreeAfterRemoveEdge(List<Edge> edges, Edge exculdEdge, Node[] nodeMap) {
Disjoint disjoint = new Disjoint(nodeMap.length – 1);
for (Edge edge : edges) {
if (edge == exculdEdge) continue;
//成环则不是树
if (disjoint.isSame(edge.s, edge.t)) {
return false;
}
disjoint.join(edge.s, edge.t);
}
return true;
}
public static Edge getRemoveEdge(List<Edge> edges, Node[] nodeMap) {
int length = nodeMap.length – 1;
Disjoint disjoint = new Disjoint(length);
for (Edge edge : edges) {
if (disjoint.isSame(edge.s, edge.t)) return edge;
disjoint.join(edge.s, edge.t);
}
return null;
}
}
No responses yet