[kuangbin带你飞]专题一 简单搜索 A - 棋盘问题

简单的DFS，不过还是挺开心的！
哈哈！
POJ宕机了，在OpenJ_Bailian上提交的（ https://vjudge.net/problem/OpenJ_Bailian-1321 ）

可以先看一下N皇后问题再做这道题，N皇后问题最初是八皇后问题，很经典的问题，可以百度一下背景故事，蛮好玩的：

题目：
https://vjudge.net/problem/HDU-2553

题解：
N皇后问题(DFS) HDU - 2553【详记】: https://blog.csdn.net/qq_41246972/article/details/86768920
N皇后问题的两个最高效的算法: https://blog.csdn.net/hackbuteer1/article/details/6657109

另外不太懂DFS或者递归思想的，可以试着用递归写个代码输出组合（例如输入3，输出123,1,2,3,12,13,23），就是排列组合中的组合，应该对理解这种思想有帮助：

1、使用DFS（深搜）遍历所有的序列所有的子组合（子序列）（排列组合中的组合）https://blog.csdn.net/qq_41246972/article/details/86750594

2、DFS——组合与排列
https://blog.csdn.net/cqbzlytina/article/details/78646018#枚举组合combination

以下是我的AC代码

速度还可以：

#include<vector> 
#include<string>
#include<utility>
#include<iostream>
using namespace std;
int n,k,ans,put[8+1],vec_size,put_1[8+1],re=1;  
vector<pair<int,int>> chess_position;
bool is_here_ok(int line,int row)
{ for(int i=0;i<line;i++) if(put[i]==row) return false;return true;
}
void dfs(int line,int i)
{if(line==k){ans++;return;} for(;i<vec_size;i++)if(chess_position[i].first!=put_1[line-1]||(chess_position[i].first==0&&re))if(is_here_ok(line,chess_position[i].second)){re=0;put[line]=chess_position[i].second;put_1[line]=chess_position[i].first;dfs(line+1,i+1); }re=1;return;
}
void solve()
{for(int i=0;i<n;i++){string input;cin>>input;getchar();for(int j=0;input[j];j++)if(input[j]=='#') {pair<int,int> res (i,j);chess_position.push_back(res);}  } vec_size=chess_position.size(); dfs(0,0);cout<<ans<<endl; return;
}
int main()
{while(true){cin>>n>>k;getchar();if(n==-1||k==-1) return 0;ans=0;solve();chess_position.clear(); } 
} 

哈哈，毕竟是部落格嘛！主要还是日志、记录为主，题解为辅，索性把草稿纸也拍上来，BLOG嘛
?