FDS

Yanrqin · 2019-01-29 12:08:12 · 个人记录

Day2

dfs

1.扫雷游戏

代码

#include<bits/stdc++.h>
using namespace std;
long long ans,n,m,i,sx,sy,tx,ty,t,l,d,a[101][101],vis[101][101];
int dx[]={1,0,-1,0},dy[]={0,-1,0,1};//标记
void search(int x,int y)
{
    if(x==tx&&y==ty){
        ans++;//求方案
        return ;
    }
    for(int i=0;i<4;i++){
        int z=x+dx[i],g=y+dy[i];
        if(a[z][g]==0&&vis[z][g]==0&&z>=1&&z<=n&&g>=1&&g<=m){
            vis[z][g]=1;
            search(z,g);//往下搜
            vis[z][g]=0;//回溯
        }
    }
}
int main()
{
    cin>>n>>m>>t>>sx>>sy>>tx>>ty;
    for(i=1;i<=t;i++)
    {
        cin>>l>>d;
        a[l][d]=1;
    }
    vis[sx][sy]=1;
    search(sx,sy);
    cout<<ans;
    return 0;

}

2.八皇后

分析 x一行仅一个固定

搜索i

判断x轴与y轴的关系

代码

#include<bits/stdc++.h>
using namespace std;
int n,v1[100],v2[100],v3[100],a[100000],ans;
void dfs(int x)
{
    if(x>n)//过终点
    {
        ans++;
        if(ans<=3)
        {
            for(int i = 1 ; i <= n ; i++)cout<<a[i]<<" ";
            cout<<endl;
        }
    }
    for(int i=1 ; i <= n ; i++)
    {
        if(v1[i]==0  && v2[(x-i+n)]==0 && v3[x+i]==0)
        {
            a[x]=i;
            v1[i]=1;   
            v2[(x-i+n)]=1;  
            v3[x+i]=1;
            dfs(x+1);
            v1[i]=0;   
            v2[(x-i+n)]=0; 
             v3[x+i]=0;//回溯
        }

    }
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<ans;
    return 0;
}