题解 | 小红的扫雷游戏

#include<bits/stdc++.h>
using namespace std;
const int N=6;
char mp[N][N];
bool vis[N][N];
bool if_X[N][N];
int num_X[N][N];
int ssum;

void dfs(int num)
{
	if(num==16)
	{
		bool pd=true;
		int mb,res;
		for(int i=1;i<=4;i++)
		{
			for(int j=1;j<=4;j++)
			{
				if(mp[i][j]>='0'&&mp[i][j]<='8')
				{
					mb=mp[i][j]-'0';
					res=0;
					res+=if_X[i-1][j-1]==1?1:0;
					res+=if_X[i-1][j]==1?1:0;
					res+=if_X[i-1][j+1]==1?1:0;
					res+=if_X[i][j-1]==1?1:0;
					res+=if_X[i][j+1]==1?1:0;
					res+=if_X[i+1][j-1]==1?1:0;
					res+=if_X[i+1][j]==1?1:0;
					res+=if_X[i+1][j+1]==1?1:0;
					if(mb!=res)
					{
						pd=false;
					}
				}
			}
		}
		if(pd)
		{
			ssum++;
			for(int x=1;x<=4;x++)
			{
				for(int y=1;y<=4;y++)
				{
					if(if_X[x][y])
					{
						num_X[x][y]++;
					}
				}
			}
		}
		return;
	}
	int x=num/4+1;
	int y=num%4+1;
	if_X[x][y]=false;
	dfs(num+1);
	if(!(mp[x][y]<='8'&&mp[x][y]>='0'))
	{
		if_X[x][y]=true;
		dfs(num+1);
	}
}

void solve()
{
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			cin>>mp[i][j];
		}
	}
	dfs(0);
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			if(mp[i][j]>='0'&&mp[i][j]<='8')
			{
				cout<<mp[i][j];
			}
			else{
				if(ssum>0&&num_X[i][j]==ssum)
				{
					cout<<'X';
				}
				else if(num_X[i][j]==0)
				{
					cout<<"O";
				}
				else
				{
					cout<<mp[i][j];
				}
			}
		}
		cout<<endl;
	}
}

int main()
{
	solve();
	return 0;
}