题解 第十六届蓝桥杯C/C++A组第二题黑白棋

DFS实现

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

int vis[10][10];//1是黑，0表示白 

bool dfs(int sum,int w,int b)
{
	if(sum==36)
	{
		if(w==18&&b==18)
		{
			if(!(vis[1][1]==1&&vis[1][2]==0&&vis[1][4]==0&&vis[2][4]==0&&vis[3][5]==0&&vis[3][6]==0&&vis[5][3]==1&&vis[5][6]==1&&vis[6][2]==0&&vis[6][5]==1))return false;
			for(int i=1;i<=6;i++)
			{
				int p = vis[i][1]+vis[i][2]+vis[i][3]+vis[i][4]+vis[i][5]+vis[i][6];
				if(p!=3)return false;
				int q = vis[1][i]+vis[2][i]+vis[3][i]+vis[4][i]+vis[5][i]+vis[6][i];
				if(q!=3)return false;
				for(int j=1;j<=4;j++)
				{
					if(vis[i][j]==vis[i][j+1]&&vis[i][j]==vis[i][j+2])return false;
					if(vis[j][i]==vis[j+1][i]&&vis[j][i]==vis[j+2][i])return false;
				} 
				for(int k=1;k<=6&&k!=i;k++)
				{
					int m = (vis[i][1]==vis[k][1])+(vis[i][2]==vis[k][2])+(vis[i][3]==vis[k][3])+(vis[i][4]==vis[k][4])+(vis[i][5]==vis[k][5])+(vis[i][6]==vis[k][6]); 
					if(m==6)return false;
					int n = (vis[1][i]==vis[1][k])+(vis[2][i]==vis[2][k])+(vis[3][i]==vis[3][k])+(vis[4][i]==vis[4][k])+(vis[5][i]==vis[5][k])+(vis[6][i]==vis[6][k]);
					if(n==6)return false;
				}
			}
			return true;//注意！！！
		}
		return false;注意！！！
	}
	int x = sum/6+1;
	int y = sum%6+1;
	vis[x][y] = 1;
	if(dfs(sum+1,w,b+1))
		return true;
	else
	{
		vis[x][y] = 0;
		return dfs(sum+1,w+1,b); 		
	}
}


int main()
{
	if(dfs(0,0,0))
	{
		for(int i=1;i<=6;i++)
		{
			for(int j=1;j<=6;j++)
			{
				cout<<vis[i][j];
			}
		}
	}
}