题目描述

有一个 R 行 C 列的二维数组 board ，如果board[i][j]= 'R' 则表示第 i 行第 j 列的格子是石头，如果 board[i][j]= '.' 则表示第 i 行第 j 列的格子是空地。

石头 A 和石头 B 是 冲突 的前提是同时满足如下的所有条件：

1. 石头 A 和石头 B 的颜色不同。
2. 石头 A 和石头 B 在同一行或者同一列。
3. 石头 A 与石头 B 之间没有其他的石头。

你要对所有的石头进行染色，但必须保证所有的石头都不能有 冲突 。在满足上述的所有条件的前提下，你希望用到的颜色种类越多越好，输出最多的颜色种类。

输入格式

多组测试数据。

第一行，一个整数G，表示有G组测试数据。1 <= G <= 10。

每组测试数据格式如下：

第一行，两个整数 R 和 C 。 1 <= R,C <= 20。

接下来是 R 行 C 列的二维数组 board 。board[i][j]='R'或 '.'

输出格式

共 G 行，每行一个整数。

样例

3
3 4
.R.R
R.R.
.R.R
1 15
RRRRRRRRRRRRRRR
6 15
...............
...............
...............
...............
...............
...............

2
1
0

完善程序

#include<bits/stdc++.h>
using namespace std;
string s[21];
bool f[21][21];
int r,c,tail,head;
struct Point
{
	int r,c;
}q[1000];
void bfs()
{
	int x,y;
	Point t;
	while(head<tail) // 判断队列是否为空
	{
		t = q[head++]; //取出队首，然后弹出队首
		
		x = t.r;
		y = t.c;
		for(int i=1;i<=r;i++)
		{
			if( 填空(1) &&s[i][y]=='R'){
				f[i][y] = true;
				q[tail].r = 填空(2);
				q[tail].c = 填空(3);
				填空(4);
			}
		}

		for(int j=1;j<=c;j++)
		{
			if(!f[x][j]&& 填空(5) ){
				f[x][j] = true;
				q[tail].r = 填空(6);
				q[tail].c = 填空(7);
				填空(4);
			}
		}
	}
}
int main()
{
	int g,cnt;
	cin>>g;
	while(g--)
	{
		cin>>r>>c;
		for(int i=1;i<=r;i++)
		{
			cin>>s[i];
			s[i] = '.' + s[i];  //为了从下标 1 开始计算 ，前面随便加点东西 
		}
		//针对每一组新的数据，都要让 f 数组复位。 f 数组是记录着一块石头是否已经被染色 
		memset(f,false,sizeof(f));
		cnt = 0;
		
		for(int i=1;i<=r;i++)
		{
			for(int j=1;j<=c;j++)
			{
				if((填空(8)&&!f[i][j])
				{
					q[0].r = i;
					q[0].c = j;
					f[i][j] = true;
					head=0;
					tail = (填空(9);
					
					cnt = (填空(10);
					bfs();			
				}
			}
		}
		printf("%d\n",cnt);
	}

	return 0;
}

填空(1): {{ input(1) }}

填空(2): {{ input(2) }}

填空(3): {{ input(3) }}

填空(4): {{ input(4) }}

填空(5): {{ input(5) }}

填空(6): {{ input(6) }}

填空(7): {{ input(7) }}

填空(8): {{ input(8) }}

填空(9): {{ input(9) }}

填空(10): {{ input(10) }}