剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

  1. class Solution {
  2.     int m,n;
  3.     char[] c;
  4.     boolean[][] visited;
  5.     char[][] board;
  6.     int[][] directions=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
  8.     public boolean exist(char[][] board, String word) {
  9.         this.board=board;
  10.         m=board.length;
  11.         n=board[0].length;
  12.         c=word.toCharArray();
  13.         visited=new boolean[m][n];
  15.         for(int i=0;i<m;i++){
  16.             for(int j=0;j<n;j++){
  17.                 if(board[i][j]==c[0]){
  18.                     visited[i][j]=true;
  19.                     if(backtrack(i,j,1)) return true;
  20.                     visited[i][j]=false;;
  21.                 }
  22.             }
  23.         }
  24.         return false;
  25.     }
  27.     private boolean backtrack(int i,int j,int next){
  28.         if(next==c.length) return true;
  29.         for(int[] dir:directions){
  30.             int x=i+dir[0];
  31.             int y=j+dir[1];
  32.             if(x>=0&&y>=0&&x<m&&y<n&&c[next]==board[x][y]&&!visited[x][y]){
  33.                 visited[x][y]=true;
  34.                 if(backtrack(x, y, next+1)) return true;
  35.                 visited[x][y]=false;
  36.             }
  37.         }        
  38.         return false;
  39.     }
  40. }

剑指 Offer 13. 机器人的运动范围

剑指 Offer 13. 机器人的运动范围

  1. class Solution {
  2.     boolean[][] reachable;
  3.     boolean[][] checked;
  4.     int m,n,k;
  6.     public int movingCount(int m, int n, int k) {
  7.         this.m=m;
  8.         this.n=n;
  9.         this.k=k;
  10.         reachable =new boolean[m][n];
  11.         checked=new boolean[m][n];
  12.         dfs(0,0);
  13.         int count=0;
  14.         for(int i=0;i<m;i++){
  15.             for(int j=0;j<n;j++){
  16.                 if(reachable[i][j]) count++;
  17.             }
  18.         }
  19.         return count;
  20.     }
  22.     private void dfs(int i,int j){
  23.         if(i<0||j<0||i>=m||j>=n||checked[i][j]){
  24.             return;
  25.         }
  26.         checked[i][j]=true;
  27.         if(calculate(i, j)<=k){
  28.             reachable[i][j]=true;
  29.             dfs(i+1,j);
  30.             dfs(i-1,j);
  31.             dfs(i,j+1);
  32.             dfs(i,j-1);
  33.         }else{
  34.             reachable[i][j]=false;
  35.         }
  36.     }
  38.     private int calculate(int i,int j){
  39.         int count=0;
  40.         while(i>0){
  41.             count+=i%10;
  42.             i=i/10;
  43.         }
  44.         while(j>0){
  45.             count+=j%10;
  46.             j=j/10;
  47.         }
  48.         return count;
  49.     }
  50. }

329. 矩阵中的最长递增路径

说是记忆化dfs

  1. class Solution {
  3.   public int longestIncreasingPath(int[][] matrix) {
  4.     int m = matrix.length;
  5.     if (m == 0) return 0;
  6.     int n = matrix[0].length;
  7.     int[][] note = new int[m][n];
  8.     int max = 0;
  9.     for (int i = 0; i < m; i++) {
  10.       for (int j = 0; j < n; j++) {
  11.         if (note[i][j] == 0) {
  12.           dfs(i, j, matrix, note);
  13.         }
  14.         max = Math.max(max, note[i][j]);
  15.       }
  16.     }
  17.     return max;
  18.   }
  20.   public int dfs(int i, int j, int[][] matrix, int[][] note) {
  21.     if (note[i][j] != 0) {
  22.       return note[i][j];
  23.     }
  24.     note[i][j]++;
  25.     int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  26.     for (int[] dir : directions) {
  27.       int x = i + dir[0];
  28.       int y = j + dir[1];
  29.       if (x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length && matrix[x][y] > matrix[i][j]) {
  30.         note[i][j] = Math.max(note[i][j], dfs(x, y, matrix, note) + 1);
  31.       }
  32.     }
  33.     return note[i][j];
  34.   }
  35. }