一个网站做多少内链合适,58同城网站模板下载,建立网站一般要多少钱,网站建设实施步骤题目#xff1a;
在一个给定形状的棋盘#xff08;形状可能是不规则的#xff09;上面摆放棋子#xff0c;棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列#xff0c;请编程求解对于给定形状和大小的棋盘#xff0c;摆放k个棋子的所有可行的摆…题目
在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。 每组数据的第一行是两个正整数n k用一个空格隔开表示了将在一个n*n的矩阵内描述棋盘以及摆放棋子的数目。 n 8 , k n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状每行有n个字符其中 # 表示棋盘区域 . 表示空白区域数据保证不出现多余的空白行或者空白列。 Output 对于每一组数据给出一行输出输出摆放的方案数目C 数据保证C2^31。 Sample Input 2 1 #. .# 4 4 …# ..#. .#.. #… -1 -1 Sample Output 2 1
分析与解答
kn,我觉得这个和八皇后不同一点就是八皇后列从第一行一直找到最后第n行但是这个可以在某一行不放棋子。于是我们dfs里面就要考虑写一个二重循环行和列都要考虑到我们假设固定行就是说每次行从第x行开始就算回溯了还可以从第xi行继续调用从而考虑到所有情况 由于是一行一行的调用因此已经放置的棋子必然不再同一行那现在就需要考虑怎么整一个条件能够去判断是不是在同一列额当然了用一个标记数组visit如果如果标志数组visit[j]0说明第j列没有用过那我们就可以大胆的放到第j列了 dfsxy的意思是在第x行准备放第y1个棋子额就是现在已经放了y个棋子了我们固定了这第x行从第一列开始找我们放棋子的条件是!visit[j]mp[i][j]’#’找到一满足条件的列我们就把棋子放这一列上放完这一行的棋子我们就继续递归找下一行递归完了还要清除标志数组因为除了在第x行的第j列放棋子仍有可能在其他列仍然能放棋子。而dfs的返回条件就是现在放的棋子个数y已经等于k了那就return了
代码参考 https://www.cnblogs.com/ECJTUACM-873284962/p/6747947.html
#includeiostream
#include algorithm
#include stdio.h
#include string.h
using namespace std;
int visit[20];
char mp[20][20];
int ans;
int k;
int n;
int DFS(int x,int y)
{if(yk){ans;return 0;}for(int ix;in;i){for(int j0;jn;j){if(!visit[j]mp[i][j]#){visit[j]true;DFS(i1,y1);visit[j]false;}}}return 0;
}
int main()
{while(cinnk){if(n-1k-1)break;memset(visit,false,sizeof(visit));memset(mp,false,sizeof(mp));for(int i0;in;i)cinmp[i];ans0;DFS(0,0);coutansendl;}return 0;
}
