[DFS]棋盘问题-POJ 1321([DFS] chessboard problem – POJ 1321)

当初学的时候就没学好,现在再学一次。
不过这一次要学的更深。毕竟是健康人了

当初学的时候就没学好,现在再学一次。
不过这一次要学的更深。毕竟是健康人了

从零开始的算法生活!

Description

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。
n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

Output

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

#include<iostream>
#include<string>
using namespace std;
char mapa[10][10];
int n,k;
long long ans=0;
bool vis[10];
void dfs(int x,int num){
	if(num==k) {
		ans++;//棋子摆完了→方法多了一种
		return;//没啥干的就洗洗睡吧
	}
	if(x>n) return;
        //如何搜?在一个地方只有两种决策→摆还是不摆
	for(int i=1;i<=n;i++){//摆了!
		if(mapa[x][i]=='#'&&vis[i]){//能摆不?
			vis[i]=0;//标记为来过
			dfs(x+1,num+1);//摆
			vis[i]=1;//恢复初始
		}//思考 为什么vis用一维的?
	}
	dfs(x+1,num);//不摆!
}
int main(){
	while(cin>>n>>k&&n!=-1&&k!=-1){
		ans=0;
		memset(vis,1,sizeof(vis));//初始化放在前面
                //实践证明即使是全局变量也要先初始化 “没有初始化的变量是不安全的”
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				cin>>mapa[i][j];//读入棋盘
			}
		dfs(1,0);//从第一行开始摆,此时摆了0个棋子
		cout<<ans<<endl;
	}
	return 0;
}
————————

I didn’t learn it well when I first learned it. Now learn it again.
But this time I learned more. After all, he is a healthy man

I didn’t learn it well when I first learned it. Now learn it again.
But this time I learned more. After all, he is a healthy man

Algorithm life from scratch!

Description

Put pieces on a chessboard of a given shape (the shape may be irregular), and there is no difference between the pieces. It is required that any two pieces cannot be placed in the same row or column in the chessboard. Please program to solve all feasible placement schemes C for placing K pieces for a chessboard of given shape and size.

Input

The input contains multiple sets of test data.
The first row of each group of data is two positive integers, N K, separated by a space, indicating the chessboard to be described in an n * n matrix and the number of pieces to be placed.
n <= 8 , k <= n
When it is – 1 – 1, it indicates the end of input.
The following N lines describe the shape of the chessboard: each line has n characters, where # represents the chessboard area and. Represents the blank area (the data ensures that there are no redundant blank lines or blank columns).

Output

For each group of data, a row of output is given, and the number of output schemes C (data guarantee C & lt; 2 ^ 31).

#include<iostream>
#include<string>
using namespace std;
char mapa[10][10];
int n,k;
long long ans=0;
bool vis[10];
void dfs(int x,int num){
	if(num==k) {
		ans++;//棋子摆完了→方法多了一种
		return;//没啥干的就洗洗睡吧
	}
	if(x>n) return;
        //如何搜?在一个地方只有两种决策→摆还是不摆
	for(int i=1;i<=n;i++){//摆了!
		if(mapa[x][i]=='#'&&vis[i]){//能摆不?
			vis[i]=0;//标记为来过
			dfs(x+1,num+1);//摆
			vis[i]=1;//恢复初始
		}//思考 为什么vis用一维的?
	}
	dfs(x+1,num);//不摆!
}
int main(){
	while(cin>>n>>k&&n!=-1&&k!=-1){
		ans=0;
		memset(vis,1,sizeof(vis));//初始化放在前面
                //实践证明即使是全局变量也要先初始化 “没有初始化的变量是不安全的”
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				cin>>mapa[i][j];//读入棋盘
			}
		dfs(1,0);//从第一行开始摆,此时摆了0个棋子
		cout<<ans<<endl;
	}
	return 0;
}