棋盘问题——1321

题目

题目传送
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放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*nstatic 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;//方案数目加1return;}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);//搜索下一行，并且当前棋子数目加1visited[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，那么还是搜得是第二行，就会出问题。