考试周后的第一发 写搜索题找手感
题意：给你一个n*n的棋盘及其放棋子的位置 给定旗子数目 问在满足条件下 能够有多少种不同放棋子的方法 写了一发DFS 差点写炸 不断搜索判断是否符合题意即可；
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef struct node {
int x;
int y;
} node;
char a[100][100];
node b[100];
int first[1005];
int k;
int sum=0;
bool vis[100];
void dfs(int e,int t,int l) {
int w;
t++;
if(t==1) {
vis[e]=1;
}
if(t==k) {
sum++;
return ;
}
for(int i=e+1; i<=l; i++) {
if(vis[i]==0) {
int flag=0;
w=e;
while(first[w]!=-1) {
if(b[i].x==b[w].x||b[i].y==b[w].y) {
flag=1;
break;
}
w=first[w];
}
if(flag==0) {
first[i]=e;
dfs(i,t,l);
}
}
}
}
int main() {
int n;
while(cin>>n>>k&&(n!=-1&&k!=-1)) {
int p=0;
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++) {
getchar();
for(int j=1; j<=n; j++) {
scanf("%c",&a[i][j]);
if(a[i][j]=='#') {
p++;
node t;
t.x=i;
t.y=j;
b[p]=t;
}
}
}
b[0].x=0;
b[0].y=0;
sum=0;
first[0]=-1;
dfs(0,-1,p);
cout<<sum<<endl;
}
return 0;
}