DFS回溯题：棋盘问题

本是古典何须时尚 2023-10-06 19:26 15阅读 0赞

## DFS回溯题：棋盘问题 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_13_color_FFFFFF_t_70_g_se_x_16]

#### 思路： ####

该题为dfs回溯题，我们按行遍历，注意到不是每一行都必须放棋子，根据处理该问题的思路不同，可以有两种不同的方式解题

两种思路都需要知道的信息有：每一列是否能放棋子（用数组表示），棋盘上的某个点是否能放棋子（用数组表示），当前已经放了多少个棋子

（1）思路一：不是每一行都必须放棋子，则每一行都有两种情况：选择在该行放棋子和不在该行放棋子。  
  dfs函数的参数有当前所遍历的行，当前已经放置的棋子数，需要放置的棋子数k，棋盘维数n，当已经放置k个棋子或当前行超出棋盘维数时返回。  
  在dfs函数中，先执行放棋子的情况，遍历当前行的所有列，找到可以放棋子的位置，放置棋子，接着调用dfs时，放置棋子数+1，行数+1。dfs返回时进行回溯，取消列标记。在执行完放棋子的情况后，执行不放棋子的情况，即调用dfs，行数+1，但放置棋子数不变

（2）思路二：我们需要知道上一次放置棋子是在哪一行，设为last，在dfs中，我们遍历last之后的所有行，这样就不会遗漏，能遍历出所有情况。在主函数中找到第一个能放棋子的行，将该行作为dfs的起点即可

#### 代码： ####

（1）思路一：

import java.util.*;
    
    public class Main {
        
    
        static int[] column = new int[9];
        static int[][] table = new int[9][9];
        static long[] ans = new long[1];
    
        public static void main(String[] args) {
        
            int n, k, i, j;
            String s;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                ans[0] = 0;
                n = scanner.nextInt();
                k = scanner.nextInt();
                Arrays.fill(column, 0);
                scanner.nextLine();
                for (i = 0;i < n;i++) {
        
                    s = scanner.nextLine();
                    for (j = 0;j < n;j++) {
        
                        if (s.charAt(j) == '#') {
        
                            table[i][j] = 1;
                        } else {
        
                            table[i][j] = 0;
                        }
                    }
                }
                dfs(0, n, k, 0);
                System.out.println(ans[0]);
            }
        }
    
        static void dfs(int i, int n, int k, int count) {
        
            if (count == k) {
        
                ans[0]++;
                return;
            }
            if (i >= n) {
        
                return;
            }
            int j;
            for (j = 0;j < n;j++) {
        
                if (column[j] == 0 && table[i][j] == 1) {
        
                    column[j] = 1;
                    dfs(i + 1, n, k, count + 1);
                    column[j] = 0;
                }
            }
            dfs(i + 1, n, k, count);
        }
    }

（2）思路二：

import java.util.*;
    
    public class Main {
        
    
        static int[] column = new int[9];
        static int[][] table = new int[9][9];
        static long[] ans = new long[1];
    
        public static void main(String[] args) {
        
            int n, k, i, j;
            String s;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                ans[0] = 0;
                n = scanner.nextInt();
                k = scanner.nextInt();
                Arrays.fill(column, 0);
                scanner.nextLine();
                for (i = 0;i < n;i++) {
        
                    s = scanner.nextLine();
                    for (j = 0;j < n;j++) {
        
                        if (s.charAt(j) == '#') {
        
                            table[i][j] = 1;
                        } else {
        
                            table[i][j] = 0;
                        }
                    }
                }
                for (i = 0;i < n;i++) {
        
                    for (j = 0;j < n;j++) {
        
                        if (table[i][j] == 1) {
        
                            dfs(i, n, k, 0, i - 1);
                            break;
                        }
                    }
                    break;
                }
    
                System.out.println(ans[0]);
            }
        }
    
        static void dfs(int i, int n, int k, int count, int last) {
        
            if (count == k) {
        
                ans[0]++;
                return;
            }
            if (i >= n) {
        
                return;
            }
            int j, line;
            for (line = last + 1;line < n;line++) {
        
                for (j = 0;j < n;j++) {
        
                    if (column[j] == 0 && table[line][j] == 1) {
        
                        column[j] = 1;
                        dfs(line + 1, n, k, count + 1, line);
                        column[j] = 0;
                    }
                }
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/273c53dbc41b4e01b9673c60906d8d39.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0ecfba97df9f4cae83b879e339337813.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_13,color_FFFFFF,t_70,g_se,x_16