分析: 本题给出棋盘分布以及落子数目, 让我们求出在棋子不同行不同列摆放的情况下, 有几种落子方式.
本题我们利用 DFS 算法, 编写一个递归函数. 从第一行第一列的位置开始在列内扫描, 如果找到合适位置就落子, 然后把这一列标记, 表示这一列不能够再次落子.
这样之后, 将前面落子位置往右往下移一位, 在这个新位置调用递归函数. 当棋子全部用完, 则方案数加 1.
PS: 要注意理解整个过程的深度优先搜索思路, 这样子有利于理解代码.
- #include<iostream>
- #include<cstring>
- using namespace std;
- const int maxn=10;
- char chessboard[maxn][maxn];
- bool visit[maxn];// 用于标记列是否还能够放下棋子
- int ans;// 表示方案数
- int k;// 表示棋子数目
- int n;// 表示棋盘的大小
- int DFS(int row,int nums_of_chess){//row 代表当前行, nums_of_chess 代表已经使用的棋子数目
- if(nums_of_chess==k){
- ans++;
- return 0;
- }
- for(int i=row;i<n;i++)
- for(int j=0;j<n;j++)
- if(!visit[j]&&chessboard[i][j]=='#'){// 如果这一列没有被标记, 而且这个位置是棋盘位置
- visit[j]=true;// 将这一列标记
- DFS(i+1,nums_of_chess+1);// 递归调用函数
- visit[j]=false;// 此处函数已经返回, 应该将列标记还原, 这样子才能够不影响下一行的过程判定
- }
- return 0;
- }
- int main(){
- while(cin>>n>>k){
- if(n==-1&&k==-1) break;
- memset(visit,false,sizeof(visit));
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++)
- cin>>chessboard[i][j];
- ans=0;
- DFS(0,0);
- cout<<ans<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2765347.html