第一场排位赛 G题 BoardGame

2015Tishreen- Board Game

以本题为例总结dfs

核心代码

//这里容易出错的点：dfs返回的位置是 [0,n)可以看成在n的位置返回
void dfs(int x,int y......)
{
	if(判断条件+边界)
	{
		//back
	}
	for(循环)
	{
		if(标记)
		//标记
		//下一个步骤
		//取消标记
	}
	//列举完所有情况，返回
}

上代码
对二位数组顺序遍历的小技巧：step从[0,n)进行输入，step/column 为列号 step%raw 为 横号

这题变式在于我们只需要找到一个解，并且在最终返回的有两种情况：满足，不满足，所以采用bool dfs的策略，若成功直接返回到步骤一然后退出循环，若不成功，返回上一层继续进行循环
很巧妙的实现回溯！

#include
using namespace std;
int a[20][20];
int vis[20];

bool is_ok()
{
	int t[8]={0};
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			t[i]+=a[i][j];
			t[j+4]+=a[i][j];	
		}	
	}	
	for(int i=1;i<8;i++)
	{
		if(t[i]!=t[i-1])
		{
			return 0;
		}
	}
	return 1;
} 

bool dfs(int step)
{
	if(step==16)
	{
		if(is_ok())
		{
			return 1;	
		} else
		{
			return 0;
		}
	}else
	{
		if(a[step/4][step%4]==-1)
		{
			for(int i=1;i<=16;i++)
			{
				if(!vis[i])
				{
					vis[i]=1;
					a[step/4][step%4]=i;
					if(dfs(step+1)) return 1;
					vis[i]=0;
					a[step/4][step%4]=-1;
				}
			}
		}else
		{
			if(dfs(step+1)) return 1;
		}		
	}
	return 0;	//为什么这里要return 0 
}
void solve(int k)
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			cin>>a[i][j];
			if(a[i][j]!=-1)
			{
				vis[a[i][j]]=1;
			}
		}
	}
	dfs(0);
	cout<<"Case "<>kase;
	for(int i=1;i<=kase;i++)
	{
		memset(vis,0,sizeof vis);
		solve(i);
		if(i!=kase)
		{
			cout<