求助站外题

题目描述：
 

给你一个黑白棋盘，棋盘上有些位置已经放了黑子或者白子，现在问你，有没有一种放置方案可以用黑子或者白子放满整个棋盘，使得没有两个相邻的格点放了同色的棋子。

 

输入格式：
多组测试数据

每组数据

第一行输入两个整数n,m
接下来n行每行输入一个长度为m的字符串.

一共有’W’, ‘B’, ‘?’三种字符，W表示白子，B表示黑子。’?’表示还没有放子

 

输出格式：
如果存在一种方案，输出”Possible”

如果不存在输出”Impossible”

 

样例输入：
3 3
W?W
??B
???
3 2
W?
??
B?
样例输出：
Possible
Impossible
 

约定：
1<=n,m<=100

#include<bits/stdc++.h> 
using namespace std;
char a[110][110];
int n,m;
bool c;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y,char in)
{
	if(x<1 || x>n || y<1 || y>n)
	{
		return;
	}
	a[x][y]=in;
	for(int k=0;k<4;k++)
	{
		if(a[x+dx[k]][y+dy[k]]==in)
		{
			c=false;
			return;
		}
		else if(a[x+dx[k]][y+dy[k]]=='?')
		{
			if(in=='W')
				dfs(x+dx[k],y+dy[k],'B');
			else
				dfs(x+dx[k],y+dy[k],'W');
		}
	}
}
int main()
{
    while(cin>>n>>m)
    {
    	c=true;
    	for(int i=0;i<110;i++)
	    {
	    	for(int j=0;j<110;j++)
	    	{
	    		a[i][j]=0;
			}
		}
    	bool can=true;
	    for(int i=1;i<=n;i++)
	    {
	    	for(int j=1;j<=m;j++)
	    	{
	    		cin>>a[i][j];
			}
		}
		bool f=false;
		for(int i=1;i<=n;i++)
	    {
	    	for(int j=1;j<=m;j++)
	    	{
	    		if(a[i][j]!='?')
	    		{
	    			f=true;
	    			if(a[i][j]=='W')
	    			{
	    				for(int k=0;k<4;k++)
	    				{
	    					dfs(i+dx[k],j+dy[k],'B');
						}
					}
					else if(a[i][j]=='B')
	    			{
	    				for(int k=0;k<4;k++)
	    				{
	    					dfs(i+dx[k],j+dy[k],'W');
						}
					}
				}
				if(!c)
				{
					cout<<"Impossible"<<endl;
					break;
				}
				else
				{
					cout<<"Possible"<<endl;
					break;
				}
			}
			if(f)
				break;
		}
	}
    return 0;
}