【剑指offer第十四天】搜索算法与回溯

小灰灰 2022-09-12 07:47 113阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]

class Solution { 
        public boolean exist(char[][] board, String word) { 
            char []tmp = word.toCharArray();
            int r = board.length;
            int c = board[0].length;
            for(int i = 0;i < r;i++){ 
                for(int j = 0;j < c;j++){ 
                    if(backtrack(board,tmp,i,j,0)) return true;
                }
            }
            return false;
        }
        public boolean backtrack(char[][] board,char[] word,int i,int j,int k){ 
            if(i < 0||i >= board.length||j < 0||j >= board[0].length||board[i][j]!=word[k]){ 
                return false;
            }
            if(k == word.length-1){ 
                return true;
            }
            board[i][j] = '\0';
            boolean res = backtrack(board,word,i+1,j,k+1)||
                          backtrack(board,word,i,j+1,k+1)||
                          backtrack(board,word,i,j-1,k+1)||
                          backtrack(board,word,i-1,j,k+1);
            board[i][j] = word[k];
            return res;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution { 
        public int movingCount(int m, int n, int k) { 
            boolean[][] visit = new boolean[m][n];
            return dfs(visit,m,n,k,0,0);
        }
        public int dfs(boolean [][]visit,int m,int n,int k,int i,int j){ 
            if(i >= m||j >= n||visit[i][j]||sum(i)+sum(j)>k){ 
                return 0;
            }
            visit[i][j] = true;
            return 1 + dfs(visit,m,n,k,i+1,j) + dfs(visit,m,n,k,i,j+1);
        }
        public int sum(int k){ 
            int res = 0;
            while(k != 0){ 
                res += k%10;
                k /= 10;
            }
            return res;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/23d28f0fcfdf4652a08d9a3b5bb92365.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAJ-alkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/bbf4fbbd369749a5b7cbfdb0a6204fda.png