【日常学习】【深搜】codevs2452 扫雷题解

野性酷女 2022-08-02 06:56 171阅读 0赞

题目来源：05年四川省选

题目描述 Description

相信大家都玩过扫雷的游戏。那是在一个n\*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，

由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

输入描述 Input Description

第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

输出描述 Output Description

一个数，即第一列中雷的摆放方案数。

样例输入 Sample Input

1 1

样例输出 Sample Output

图片可以在网上找到，格子里的数字可以是0，不影响做题

据说网上有深搜的，动归的，还有模拟的。我这里是深搜的做法。

思路就是深搜的经典思路，对于每一个格子填或不填进行搜索，再消除影响。

代码：

//mine 扫雷 暴搜第一课
    //copyright by ametake
    //感谢里奥同学友情支援~ 
    #include
       
         
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=10000+10;
    int a[maxn];
    int b[maxn];
    int n,ans=0;
    
    void dfs(int pos,int state)
    {
    //	if (pos>n)
    //	{
    //		ans++;
    //		return;
    //	}
    	if (state==1)
    	{
    		if (pos-1>0) 
    		{
    			a[pos-1]++;
    			//if (a[pos-1]!=b[pos-1]) return;
    		}
    		a[pos]++;
    		//if (a[pos]>b[pos]) return;
    		if (pos+1<=n)
    		{
    			a[pos+1]++;
    			//if (a[pos+1]>b[pos+1]) return;
    		}
    		if ((a[pos-1]!=b[pos-1])||(a[pos]>b[pos])||(a[pos+1]>b[pos+1])) return;
    		if (pos==n)
    		{
    			if (a[pos]==b[pos]) ans++;
    			return;
    		}
    		dfs(pos+1,1);
    		if (pos>0) a[pos]--;
    		a[pos+1]--;
            if (pos+2<=n) a[pos+2]--;
            dfs(pos+1,0);
    		//if (pos-1>0) a[pos-1]--;
    		//a[pos]--;
            //if (pos+1<=n) a[pos+1]--;
    	}
    	else 
    	{
    		if (pos-1>0) 
    		{
    			if (a[pos-1]!=b[pos-1]) return;
    		}
    		if (pos==n)
    		{
    			if (a[pos]==b[pos]) ans++;
    			return;
    		}
    		dfs(pos+1,1);
    		if (pos>0) a[pos]--;
    		a[pos+1]--;
            if (pos+2<=n) a[pos+2]--;
    		dfs(pos+1,0);
    	}
    }
    
    int main()
    {
    	freopen("mine.in","r",stdin);
    	freopen("mine.out","w",stdout); 
    	scanf("%d",&n);
    	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    	memset(a,0,sizeof(a));
    	dfs(1,1);
    	memset(a,0,sizeof(a));
    	dfs(1,0);
    	printf("%d\n",ans);
    	return 0;
    }

——渐霜风凄惨，关河冷落，残照当楼。