广州天河区做网站的公司,国外wordpress商城,昆明排名优化,浙江省财务开发公司官网文章目录1. 题目1.1 题目链接1.2 题目大意1.3 解题思路2. 代码2.1 Accepted 代码1. 题目
1.1 题目链接
http://poj.org/problem?id1321
1.2 题目大意
在一个给定形状的棋盘#xff08;只能在#号的位置摆放#xff09;上面摆放棋子#xff0c;棋子没有区别。要求摆放时任…
文章目录1. 题目1.1 题目链接1.2 题目大意1.3 解题思路2. 代码2.1 Accepted 代码1. 题目
1.1 题目链接
http://poj.org/problem?id1321
1.2 题目大意
在一个给定形状的棋盘只能在#号的位置摆放上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列求解对于给定形状和大小的棋盘摆放k个棋子的所有可行的摆放方案个数。
1.3 解题思路
采用回溯算法暴力枚举
2. 代码 2.1 Accepted 代码
/*** description: poj1321回溯* author: michael ming* date: 2019/7/13 13:58* modified by: */
#include iostream
#include string
using namespace std;bool a[10][10];//存储棋盘
int result[10];//存储是否存放棋子和8皇后类似
bool isok(int r, int c)//判断是否可以摆放
{for(int i r - 1; i 0; --i)//逐行向上考察每一行{if(result[i] c)//上面所有行的c列有棋子吗return false;}return true;
}void flip(int r, int num, int count, int n, int k)
{if(num k) //k个棋子都放置好了{count; //记录可行方案数return;//都放置好了没法再递归了}if(r n)return;//边界没法再递归了for(int column 0; column n; column)//r行可能有n种放法{if(a[r][column] ! 1)continue;//寻找可放置的位置if(isok(r,column)) //该放法满足要求{result[r] column;//第r行的棋子放到了column列num;//放置棋子数加1flip(r1, num, count, n, k); //放了棋子 考察下一行result[r] -1;//恢复现场这个地方不放棋子找下一种方法num--;//放置的棋子数减1}}flip(r1, num, count, n, k); //第r行不放棋子考察下一行
}
int main()
{string s;int i, j, n, k, num 0, count;while(cin n k n ! -1){count 0;//计数清零for (i 0; i n; i)//输入地图{cin s;for (j 0; j n; j){if (s[j] #)a[i][j] 1;//1的地方才可以放棋子elsea[i][j] 0;}}flip(0, num, count, n, k);cout count endl;}return 0;
}
