棋盘问题
- 题目
- Input
- Output
- 思路
- 代码
- 结果与总结
题目
题目传送
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
思路
目前只会深搜，还在缓慢挣扎中。冲冲冲！题目要求，两个棋子不能放在相同的行和列，就是，这个棋子的上下左右都不能有其它的棋子，而且只能放在棋盘上为’#'的位置， . 的位置是空白的地方，不能够放置棋子。
要创建一个map[][]数组，用来存放地图的，这次就不用开得很大了，我们在0-n的范围内搜索即可。
因为要求每一行只能有一个棋子，所以我们可以利用for循环来限制行，我们需要另外开一个数组 visited[] 这个，第i列是否插入了棋子。
对于深搜函数，先判断说，当前方案的棋子个数是不是已经达到了题目所要放的棋子数，如果是的话，就直接 ++ans【方案数目加1】，然后return即可。
如果当前的棋子数目还没有到达题目的要求，我们就继续深搜。因为传入的是第x行，这个是还没有搜索的行，我们就进行搜索，条件是当前列没有插入棋子(visited[i]==0) 而且 当前位置是 ‘#’，这样子我们就可以放入棋子。然后，把当前列给置为插入棋子了（visited[i]=1）,并且往下搜i+1行。
代码
import java.util.Scanner; public class Main{ static int n;//棋盘的大小 n*n static int k;//棋子数目 static char map[][]=new char[10][10]; static int ans; static int visited[]=new int[10];//1表示插入棋子了，0表示是没有插入棋子，visited[i] 表示第i列是否已经插入了棋子 public static void main(String[] args) { Scanner reader=new Scanner(System.in); while (reader.hasNextInt()) { ans=0;//可行方案数目 //初始化标记数组 for (int i=0;i<10;++i) visited[i]=0; n=reader.nextInt();//接收棋盘的大小 k=reader.nextInt();//棋子的数目 String blank=reader.nextLine();//接收上面的空行 if (n== -1 && k== -1) break; //存放整个棋盘 for (int i=0;i<n;++i) { String test=reader.nextLine(); for (int j=0;j<n;++j) map[i][j]=test.charAt(j); } dfs(0,0); System.out.println(ans); } } private static void dfs(int x, int count)//前面的是行，后面的是当前棋子数 { if (count>=k) { ++ans;//方案数目加1 return; } for (int i=x;i<n;++i)//因为要求在不同行，所以每次只能搜不同行的 for (int j=0;j<n;++j) //搜这一行对应的是否有位置可以放棋子 { if (check(i,j)) { visited[j]=1;//插入棋子 dfs(i+1,count+1);//搜索下一行，并且当前棋子数目加1 visited[j]=0; } } } //返回该列是否插入棋子和改位置是否能被插入棋子 private static boolean check(int a,int b) { return visited[b]==0 && map[a][b]=='#'; } }
结果与总结
ac了，虽然ac了，这道题检验出来的问题很多。对于这种搜索的条件限制还是不能够自己很好的写出来。
在dfs函数里面，我们传进来的x行，就是要搜的，然后，我们把x赋值给i，从i开始，一直搜，如果检查这一行符合条件了，即check函数返回的是true。我们需要搜的是 i+1 行。得益于一位大佬的指导，搜索是基于当前状态才能继续往下搜索的。如果说，我们传进来的x=1，即要搜第一行，然后，我们第二行搜过了，所以这个时候，要搜的是第三行，如果再利用x+1，那么还是搜得是第二行，就会出问题。
本文地址：https://blog.csdn.net/weixin_44750790/article/details/107894988
