3741 - 贵州大学第五届程序设计竞赛连通的棋子数

给定一个N * N的棋盘，计算棋盘上每一个位置的棋子在水平方向、竖直方向以及对角线方向连通的相同棋子的最大数。例如，下面的棋盘上，第1列的黑子的最大连通数都是4，而第1行的第2、3两个黑子的最大连通数是3。位于棋盘对角线上的每个白子的最大连通数都是3，等等。

<img src="http://tk.hustoj.com:80//../file://C:\Users\xujing\AppData\Roaming\Tencent\Users\57409808\QQ\WinTemp\RichOle\CI0YWHMPL4GG93@3N[@(@[E.png" />

<img src="http://tk.hustoj.com:80//../file://C:\Users\xujing\AppData\Roaming\Tencent\Users\57409808\QQ\WinTemp\RichOle\CI0YWHMPL4GG93@3N[@(@[E.png" />

<br />

Input

输入包括多组测试数据。每组测试数据的第一行包含一个整数N(0<=N<=1000)代表棋盘的大小，接下来是N行，每行包括N个字母，字母为B表示黑子，为W表示白子，为#表示该处没有棋子。N为0表示输入结束。

Output

对每组测试数据，输出N行，每行N个整数分别表示棋盘该处棋子的最大连通数，如果棋盘该处无棋子则应该输出0。

Examples

Input

5
B B B # #
B W # W W
B # W # #
B # # W #
# # # # #
0

Output

Solution C++

#include <iostream>
#include <stdio.h>
using namespace std;
char k[2005][2005];
long long n;

long long max(long long a,long long b)
{
	if (a>b) return a;
	else return b;
}

long long maxxx(long long a,long long b,long long c,long long d)
{
	return max(max(a,b),max(c,d));
}

long long dfs(long long i,long long j,char c )
{

	if (c=='#') return 0;

	long long ans1=0,ans2=0,ans3=0,ans4=0;
	for (long long s=i;s<n;s++){
		if (k[s][j]==c) ans1++;
		else break;
	}

	for (long long s=i;s>=0;s--){
		if (k[s][j]==c) ans2++;
		else break;
	}

	for (long long s=j;s<n;s++){
		if (k[i][s]==c) ans3++;
		else break;
	}
	for (long long s=j;s>=0;s--){
		if (k[i][s]==c) ans4++;
		else break;
	}


	long long anss1=0,anss2=0,anss3=0,anss4=0;
		for (long long s=0;;s++){
			if (i+s<n&&j+s<n){
				if (k[i+s][j+s]==c) anss1++;
				else break;
			} else break;
		}

		for (long long s=0;;s++){
			if (i-s>=0&&j-s>=0){
				if (k[i-s][j-s]==c) anss2++;
				else break;
			} else break;
		}
	
		for (long long s=0;;s++){
			if (i+s<n&&j-s>=0){
				if (k[i+s][j-s]==c) anss3++;
				else break;
			} else break;
		}
		for (long long s=0;;s++){
			if (i-s>=0&&j+s<n){
				if (k[i-s][j+s]==c) anss4++;
				else break;
			} else break;
		}

	return maxxx(ans1+ans2-1,ans3+ans4-1,anss1+anss2-1,anss3+anss4-1);

}



int main()
{
	
	while(~scanf("%lld",&n)&&n){
		getchar();
		for (long long i=0;i<n;i++){
			for (long long j=0;j<n;j++){
				cin>>k[i][j];
			}
		}
		
		for (long long i=0;i<n;i++){
			for (long long j=0;j<n;j++){
				if (j) printf(" ");
				printf("%lld",dfs(i,j,k[i][j]));
			}
			printf("\n");
		}

	}
	return 0;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题

3741 - 贵州大学第五届程序设计竞赛 连通的棋子数

Input

Output

Examples

Input

Output

Solution C++

3741 - 贵州大学第五届程序设计竞赛连通的棋子数