欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java数据结构算法(棋盘棋子摆放的可能形状求解)

程序员文章站 2022-06-28 17:12:45
深搜...



题目

题目传送
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放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]=='#'; } } 

结果与总结

Java数据结构算法(棋盘棋子摆放的可能形状求解)
ac了,虽然ac了,这道题检验出来的问题很多。对于这种搜索的条件限制还是不能够自己很好的写出来。

在dfs函数里面,我们传进来的x行,就是要搜的,然后,我们把x赋值给i,从i开始,一直搜,如果检查这一行符合条件了,即check函数返回的是true。我们需要搜的是 i+1 行。得益于一位大佬的指导,搜索是基于当前状态才能继续往下搜索的。如果说,我们传进来的x=1,即要搜第一行,然后,我们第二行搜过了,所以这个时候,要搜的是第三行,如果再利用x+1,那么还是搜得是第二行,就会出问题。

本文地址:https://blog.csdn.net/weixin_44750790/article/details/107894988

相关标签: Java数据结构