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

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

从零开始的算法生活！

Description

Input

n <= 8 , k <= n

Output

``````#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;
}
``````