棋盘格回溯算法总结

古城微笑少年丶 2024-04-03 09:44 77阅读 0赞

通法：dfs里全是if 没有return，dfs的参数一般只需要坐标和棋盘，偶尔会有boolean\[\]\[\] 看需要  
ps: if\{1进入状态值，2进入dfs\}

### lc 79 单词搜索 ###

![在这里插入图片描述][112b7e16352945eba34461d9c1479168.png]  
res是返回值，bool类型设置为公共变量，24行不能走的地方就直接return。12行最后一个参数要加0，棋盘回溯本不用加0，这题有word相当于有长度限制，要加0，记录长度。

### lc200 岛屿问题 ###

![在这里插入图片描述][0bb799d30bf34352b30b3f59da0fd823.png]

### 迷宫问题 ###

![在这里插入图片描述][8736531203804a50849c37871dc6a8ca.png]  
![在这里插入图片描述][3d6f9d16d4344718bed4479783d440ff.png]

import java.util.Scanner;
    
    public class Solution {
        
        static char[][] qipan;
        static int[][] status;
        static int m,n;
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            m = sc.nextInt();
            n = sc.nextInt();
            qipan = new char[m][n];
            status = new int[m][n];
            sc.nextLine();
            int ox = 0,oy = 0;
            for (int i = 0; i < m; i++) {
        
                String str = sc.nextLine();
                char[] chars = str.toCharArray();
                for (int j = 0; j < chars.length; j++) {
        
                    qipan[i][j] = chars[j];
                    if(chars[j]== '0'){
        
                        ox = i;
                        oy = j;
                    }
                }
            }
            recursion(ox,oy);
            int count = 0;
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if(status[i][j] == 0) count++;
                }
    
            }
            count--;
            System.out.println(count);
        }
    
        private static void recursion(int x, int y) {
        
            if(x - 1 >=0&& status[x-1][y] ==0 && (qipan[x - 1][y] == 'D' || qipan[x - 1][y] == '.')){
        
                status[x-1][y] = 1;
                recursion(x-1,y);
            }
            if(x + 1 <= (n -1) && status[x+1][y] ==0 && (qipan[x + 1][y] == 'U' || qipan[x + 1][y] == '.')){
        
                status[x+1][y] = 1;
                recursion(x+1,y);
            }
            if(y - 1 >=0&& status[x][y-1] ==0 && (qipan[x][y - 1] == 'R' || qipan[x][y - 1] == '.')){
        
                status[x][y - 1] = 1;
                recursion(x,y - 1);
            }
            if(y + 1 <= (n -1) && status[x][y + 1] ==0 && (qipan[x][y + 1] == 'L' || qipan[x][y + 1] == '.')){
        
                status[x][y + 1] = 1;
                recursion(x,y + 1);
            }
        }
    
    }

[112b7e16352945eba34461d9c1479168.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/cb4eea3c1b3c49a488e2e708228de3ce.png
[0bb799d30bf34352b30b3f59da0fd823.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/96b34ba5afb340328077e2d91b6a03d6.png
[8736531203804a50849c37871dc6a8ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/2978aa17e8a5434a8fe39317a2714508.png
[3d6f9d16d4344718bed4479783d440ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a725086d39c24629b372cb52ce791046.png