从左上到右下

有M*N个节点的矩阵，每个节点可以向上下左右和四个斜着的方向转发数据包，每个节点转发会消耗时延值，连续两个相同的时延值可以减少一个时延值，即K个相同时延连续转发可以减少K - 1的时延值，求左上角[0,0]节点转发到右下角[m - 1, n - 1]的最短时延。
输入：
3 3 #矩阵大小
0 2 2 #数值代表时延
1 2 1
2 2 1
输出：
2

  1. import java.util.*;
  2. class Main{
  3.     static int[][] map;
  4.     static int res = Integer.MAX_VALUE;
  5.     static int[] dx = {-1,-1,-1,0,0,1,1,1};
  6.     static int[] dy = {-1,0,1,-1,1,-1,0,1};
  7.     static boolean[][] f;
  8.     public static void dfs(int bx, int by, int m, int n, int sum, int[][] map){
  9.         if(bx == m - 1 && by == n - 1){
  10.             res = Math.min(res, sum);
  11.             return;
  12.         }
  13.         for(int i = 0; i < 8; i++){
  14.             int tx = bx + dx[i];
  15.             int ty = by + dy[i];
  16.             if(tx >= 0 && tx < m && ty >= 0 && ty < n && f[tx][ty] == false){
  17.                 f[tx][ty] = true;
  18.                 if(map[tx][ty] == map[bx][by]) sum += (map[tx][ty] - 1);
  19.                 else sum += map[tx][ty];
  20.                 dfs(tx, ty, m, n, sum, map);
  21.                 if(map[tx][ty] == map[bx][by]) sum -= (map[tx][ty] - 1);
  22.                 else sum -= map[tx][ty];
  23.                 f[tx][ty] = false;
  24.             }
  25.         }
  26.     }
  27.     public static void main(String[] args){
  28.         Scanner cin = new Scanner(System.in);
  29.         int m = cin.nextInt();
  30.         int n = cin.nextInt();
  31.         f = new boolean[m][n];
  32.         map = new int[m][n];
  33.         for(int i = 0; i < m; i++){
  34.             for(int j = 0; j < n; j++){
  35.                 map[i][j] = cin.nextInt();
  36.             }
  37.         }
  38.         f[0][0] = true;
  39.         dfs(0, 0 ,m, n, map[0][0], map);
  40.         System.out.print(res);
  41.     }
  42. }

任意点到点的

输入
5 4 #矩阵大小
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
0 0 3 2 #开始点->结束点
输出 7

  1. import java.util.*;
  2. class Main{
  3.     static int[][] map;
  4.     static int res = Integer.MAX_VALUE;
  5.     static int[] dx = {-1, 0, 1, 0};
  6.     static int[] dy = {0, 1, 0, -1};
  7.     public static void dfs(int bx, int by, int ex, int ey, int m, int n, int sum, int[][] map){
  8.         if(bx == ex && by == ey){
  9.             res = Math.min(res, sum);
  10.             return;
  11.         }
  12.         for(int i = 0; i < 4; i++){
  13.             int tx = bx + dx[i];
  14.             int ty = by + dy[i];
  15.             if(tx >= 0 && tx < m && ty >= 0 && ty < n && map[tx][ty] == 0){
  16.                 map[tx][ty] = 2;
  17.                 dfs(tx, ty, ex, ey, m, n, sum + 1, map);
  18.                 map[tx][ty] = 0;
  19.             }
  20.         }
  21.     }
  22.     public static void main(String[] args){
  23.         Scanner cin = new Scanner(System.in);
  24.         int m = cin.nextInt();
  25.         int n = cin.nextInt();
  26.         map = new int[m][n];
  27.         for(int i = 0; i < m; i++){
  28.             for(int j = 0; j < n; j++){
  29.                 map[i][j] = cin.nextInt();
  30.             }
  31.         }
  32.         int bx = cin.nextInt();
  33.         int by = cin.nextInt();
  34.         int ex = cin.nextInt();
  35.         int ey = cin.nextInt();
  36.         dfs(bx, by, ex, ey, m, n, 0, map);
  37.         System.out.print(res);
  38.     }
  39. }

保留下路径

这里是用一个map记录下所有路径长度，及其对应的路径信息。然后在利用确定的最小的路径长度，取出对应的具体路径信息

import java.util.*;
class Main{
    static int[][] map;
    static int res = Integer.MAX_VALUE;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Map<Integer, ArrayList<ArrayList<Integer>>> road = new HashMap<>();
    public static void dfs(int bx, int by, int ex, int ey, int m, int n, int sum, int[][] map, ArrayList path){
        if(bx == ex && by == ey){
            res = Math.min(res, sum);
            road.put(res, new ArrayList(path));
            return;
        }
        for(int i = 0; i < 4; i++){
            int tx = bx + dx[i];
            int ty = by + dy[i];
            if(tx >= 0 && tx < m && ty >= 0 && ty < n && map[tx][ty] == 0){
                ArrayList<Integer> tmp = new ArrayList<>();
                tmp.add(tx);
                tmp.add(ty);
                path.add(tmp);
                map[tx][ty] = 2;
                dfs(tx, ty, ex, ey, m, n, sum + 1, map, path);
                map[tx][ty] = 0;
                path.remove(path.size() - 1);
            }
        }
    }
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int m = cin.nextInt();
        int n = cin.nextInt();
        map = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = cin.nextInt();
            }
        }
        int bx = cin.nextInt();
        int by = cin.nextInt();
        int ex = cin.nextInt();
        int ey = cin.nextInt();
        ArrayList<ArrayList<Integer>>  path = new ArrayList<>();
        path.add(new ArrayList(Arrays.asList(bx, by)));
        map[bx][by] = 2;
        dfs(bx, by, ex, ey, m, n, 0, map, path);
        System.out.print(res +"  "+ road.get(res).toString());
    }
}