游客 注册 | 登录
中文 | En

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

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

给定一个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 />

题目输入

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

题目输出

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

输入/输出样例

输入格式

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

输出格式

4 3 3 0 0
4 3 0 2 2
4 0 3 0 0
4 0 0 3 0
0 0 0 0 0

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;
}

Java解答

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {
	
	
	public static void main(String[] args){
		
			fun();
		
	}
	
	public static void fun(){
		Scanner sc = new Scanner(new BufferedInputStream(System.in));
		
		int n = Integer.parseInt(sc.nextLine());
		
		byte[][] bs = new byte[n][n];
		short[][] ss = new short[n][n];
		
		
		for(int i=0;i<n;i++){
			String line = sc.nextLine();
			for(int j=0,k=0;j<line.length();j+=2){
				bs[i][k++]=(byte)(line.charAt(j));
			}
		}
		seek(bs,ss);
		print(ss);
		
	}
	
	static final byte BLANK = (byte)'#';
	
	public static void print(short[][] ss){
		int n=ss.length;
		if(n==0)return;
		for(int i=0;i<n;i++){
			for(int j=0;j<n-1;j++){
				System.out.print(ss[i][j]+" ");
			}
			System.out.println(ss[i][n-1]);
		}
		
	}
	public static void seek(byte[][] bs,short[][] ss){
		int n=ss.length;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				ss[i][j]=max(seekV(bs,i,j),seekH(bs,i,j),seekDuiJiao(bs,i,j));
			}
		}
	}
	
	static short max(int a,int b,int c){
		a = Math.max(a,b);
		a=Math.max(a,c);
		return (short)a;
	}
	
	public static int seekV(byte[][] bs,int i,int j){
		if(bs[i][j]==BLANK)return 0;
		
		int n=1;
		for(int k=i-1;k>=0;k--){
			if(bs[k][j]==bs[i][j])n++;
			else break;
		}
		for(int k=i+1;k<bs.length;k++){
			if(bs[k][j]==bs[i][j])n++;
			else break;
		}
		return n;
	}
	public static int seekH(byte[][] bs,int i,int j){
		
		if(bs[i][j]==BLANK)return 0;
		
		int n=1;
		
		for(int k=j-1;k>=0;k--){
			if(bs[i][k]==bs[i][j])n++;
			else break;
		}
		for(int k=j+1;k<bs.length;k++){
			if(bs[i][k]==bs[i][j])n++;
			else break;
		}
		return n;
	}
	public static int seekDuiJiao(byte[][] bs,int i,int j){
		if(bs[i][j]==BLANK)return 0;
		
		int n=1;
		int len = i<j?i:j;
		for(int m=1;m<=len;m++){
			if(bs[i-m][j-m]==bs[i][j])n++;
			else break;
		}
		len = bs.length-i<bs.length-j?bs.length-i:bs.length-j;
		len--;
		for(int m=1;m<len;m++){
			if(bs[i+m][j+m]==bs[i][j])n++;
			else break;
		}
		return n;
	}
}
请先登陆