260

#include <iostream>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <cstring>

#define INF 1000000000

using namespace std;

string row[205];
bool trace[205][205];
int N;

struct node{
	int x;
	int y;
};

int floodFillDfs(node a)
{
	//stack<node> s;
	queue<node> s;
	map<int,int> mp;
	s.push(a);
	int i,j;
	int r =0;

	while(!s.empty())
	{
		node t= s.front();//s.top();
		s.pop();

		i=t.x; j=t.y;

		if(i>=N || i<0)
		continue;
		if(j>=N || j<0)
		continue;

		if(trace[i][j])
		continue;

		trace[i][j]=1;

		if(row[i][j]=='w')
		{
			mp[j]=1;
			//cout<<"ij = "<<i<<" "<<j<<"\n";
		}


		t.x =i-1; t.y = j;
		if(row[i][j]=='w')
		s.push(t);

		t.x =i-1; t.y = j-1;
		if(row[i][j]=='w')
		s.push(t);

		t.x =i+1; t.y = j+1;
		if(row[i][j]=='w')
		s.push(t);

		t.x =i+1; t.y = j;
		if(row[i][j]=='w')
		s.push(t);

		t.x =i; t.y = j-1;
		if(row[i][j]=='w')
		s.push(t);

		t.x =i; t.y = j+1;
		if(row[i][j]=='w')
		s.push(t);

	}

	return mp.size();
}

int main()
{
	int res;
	bool flag=false;
	int kase = 1;
	while(cin>>N)
	{
		if(N==0)
		break;

		for(int i=0;i<N;i++)
		{
			cin>>row[i];
		}

		for(int i=0;i<205;i++)
			for(int j=0;j<205;j++)
				trace[i][j]=false;

		flag =false;
		for(int i=0;i<N && flag==false;i++)
		{
				if(row[i][0]=='w')
				{
					res=0;
					memset(trace,false,sizeof(trace));
					node t;
					t.x=i;t.y=0;
					res=floodFillDfs(t);
					//cout<<res<<"\n";
					if(res==N)
					{
						flag=1;
						//cout<<"i "<<i<<"\n";
						break;
					}
				}
		}

		if(flag)
		cout<<kase++<<" W\n";
		else
		cout<<kase++<<" B\n";
	}

	return 0;
}

This can be done using both stack or queue.

Leave a Reply

Your email address will not be published. Required fields are marked *