蓝桥杯算法提高VIP-棋盘多项式 （C++代码）dfs

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n,map[9][9],cnt=0;
int check(int xx,int yy)//第x行,第y个位置
{
    int i,j,t1=0,t2=0;
    if (map[xx][yy] == 2 || map[xx][yy] == 0) //是洞
      return 1;
    for (i=xx-1; i>=1; i--) //找出0的位置
    {
        if (map[i][yy] == 0)
        {
            t1 = i;
            break;
         }
    }
    for (i=xx-1; i>=1; i--)
    {
        if (map[i][yy] == 2)//找出2的位置，2代表是棋子
        {
            t2 = i;
            break;
        }
    }
    if (t2 > t1) //2比0较近，说明不能放
    {
        return 1;
    }
    t1 = t2 = 0;
    for (i=yy-1; i>=1; i--)//同上，找2，和0 的位置
    {
        if (map[xx][i] == 0)
        {
            t1 = i;
            break;
        }
    }
    for (i=yy-1; i>=1; i--)
    {
        if (map[xx][i] == 2)
        {
            t2 = i;
            break;
        }
    }
    if (t2 > t1)
     return 1;
    return 0; //可以放
}
void dfs(int ss,int x,int sum,int pos)//放ss个棋子，x行下标，sum个棋子，pos记录下一个循环位置
{
    int i,j,t;
    if (x > n)
     return ;
    if (sum >= ss)//一种方案
    {
        cnt++;
        return ;
    }
    for (i=pos; i<=n; i++)
    {
        if (check(x,i)) //发送行列，判断是否可以放棋子
        continue;
        t = map[x][i];
        map[x][i] = 2;
        dfs(ss,x,sum+1,i+1);//增加列
        map[x][i] = t;//回溯，恢复原样
    }
    dfs(ss,++x,sum,1);//换行
}
int main()
{
    int i,j;
    cin>>n;
    for (i=1; i<=n; i++)
    for (j=1; j<=n; j++)
    {
        cin>>map[i][j];
    }
    for (i=1; ;i++)
    {
        cnt=0;
        dfs(i,1,0,1);
        if (cnt==0)
        {
            break;
        }
        cout<<cnt<<endl;
    }
    return 0;
 }