首页 > 试题广场 >

涂棋盘

[编程题]涂棋盘
  • 热度指数:2608 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小易有一块n*n的棋盘,棋盘的每一个格子都为黑色或者白色,小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画,帮助小易算算他会涂画多少个棋格。

输入描述:
输入数据包括n+1行:
第一行为一个整数n(1 ≤ n ≤ 50),即棋盘的大小
接下来的n行每行一个字符串表示第i行棋盘的颜色,'W'表示白色,'B'表示黑色


输出描述:
输出小易会涂画的区域大小
示例1

输入

3 BWW BBB BWB

输出

3
package go.jacob.day914;

import java.util.Scanner;

/**
 * [编程题]涂棋盘
 * @author Administrator
 * 循环的时候要注意,是求每一列连续相同颜***域
 */
public class Demo4 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] strs = new String[n];
		for (int i = 0; i < n; i++) {
			strs[i] = sc.next();
		}
		int max = 0;
		for (int i = 0; i < n; i++) {
			int count = 1;
			for (int j = 1; j < n; j++) {
				if (strs[j].charAt(i) == strs[j-1].charAt(i)) {
					count++;
				} else {
					if (count > max)
						max = count;
					count = 1;
				}
			}
			if (count > max)
				max = count;
		}
		System.out.println(max);
		sc.close();

	}
}


发表于 2017-09-14 11:10:49 回复(0)
import java.util.Scanner;

/*
 * 这题就是求各数组相同字符子串的最大长度
 * */
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			int n = scan.nextInt();
			String[] str = new String[n];
			for (int i = 0; i < n; i++) {
				str[i] = scan.next();
			}

			int count = 0;
			for (int j = 0; j < n; j++) {
				int c = 1;
				for (int i = 0; i < n - 1; i++) {
					if (str[i].charAt(j) == str[i + 1].charAt(j)) {
						c++;
						count = Math.max(c, count);
					} else {
						c = 1;
					}
				}

			}
			System.out.println(count);
		}
		scan.close();
	}
}


发表于 2017-04-30 13:21:54 回复(1)
package drawing;
import java.util.*;
/**
 * 这个题求的是某一列中拥有相同颜色最多的区域,其实把这道题目分解开,算法模型就是求一个数组中相同元素最多的子数组长度。
 * 比如说,数组为[1, 1, 1, 2, 2, 2, 2, 3],那么最大长度就是4。
 * 怎么求呢?
 * 建立一个辅助数组dp,里面存放的是到这个数为止,相同元素最多的子数组的长度。
 * 那么dp的值为[1, 2, 3, 1, 2, 3, 4, 1]。
 * 我们只需要保存这个数组的最大值返回即可。
 * 那么这道题就是每一列为一个数组,求每一列的相同元素最多的子数组长度,然后找出最大值返回即可。
 * @author 何嘉龙
 *
 */
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
			char[][] area = new char[n][n];
			for (int i = 0; i < n; i++) {
				char[] chas = in.next().toCharArray();
				for (int j = 0; j < n; j++) {
					area[i][j] = chas[j];
				}
			}
			System.out.println(getMaxArea(area, n));
		}
		in.close();
	}
	public static int getMaxArea(char[][] arr, int n) {
		int maxArea = 0;
		for (int i = 0; i < n; i++) {
			int count = 1;
			int maxCount = 1;
			int[] dp = new int[n];
			dp[0] = 1;
			for (int j = 1; j < n; j++) {
				if (arr[j][i] == arr[j - 1][i]) {
					count++;
					dp[j] = count;
				} else {
					count = 1;
					dp[j] = count;
				}
				if (dp[j] > maxCount) {
					maxCount = dp[j];
				}
			}
			if (maxCount > maxArea) {
				maxArea = maxCount;
			}
		}
		return maxArea;
	}
}

发表于 2017-04-15 20:34:29 回复(2)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
	using namespace std;
	int n;
	while (cin >> n) {
		vector<vector<char> > matrix(n, vector<char>(n));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> matrix[i][j];
			}
		}
		int max = 0;
		for (int i = 0; i < n; i++) {
			int ret = 1;
			for (int j = 0; j < n - 1; j++) {
				if (matrix[j][i] == matrix[j + 1][i]) {
					ret++;
					if (ret > max) {
						max = ret;
					}
				}
				else {
					ret = 1;
				}
			}
		}
		cout << max << endl;
	}
	return 0;
}

发表于 2017-05-02 16:02:02 回复(0)
import sys,re
n=int(sys.stdin.readline().strip())
color=[]
for i in range(n):
    color.append([ i for i in raw_input().strip()])
def trans(m):
    for i in range(len(m)):
        for j in range(i):
            m[i][j], m[j][i] = m[j][i], m[i][j]
    return m
color_1=trans(color)
color_2=[]
for i in range(n):
    color_2.append(''.join(color_1[i]))
res,countB,countW=[],0,0
for i in range(n):
    countB=len(max(re.split(r'W*',color_2[i]),key=len))
    countW=len(max(re.split(r'B*',color_2[i]),key=len))
    res.append(max(countB,countW))
res.sort()
print(res[-1])
发表于 2018-05-17 16:57:55 回复(0)
#include <stdio.h>
#define N 50
int max(int a, int b);
int main(){
	int n,i,j; //棋盘的大小
	char str[N][N];
    scanf("%d",&n);
    getchar();
    for(i=0;i<n;i++){
    	gets(str[i]);
    }
    int max_num=0;
    for(j=0;j<n;j++){   //j是列 
    	int w_num=0,b_num=0;
    	for(i=0;i<n;i++){  // i是行 
    		if(i==0){
    			w_num=1; b_num=1;
		    }else{
	    		if(str[i][j]==str[i-1][j]){
		    		if(str[i][j]=='W') w_num++;
		    		if(str[i][j]=='B') b_num++;
	    		    if(i==n-1){
    		    		max_num = max(max(b_num,w_num), max_num);
    		    		w_num=0;b_num=0;
    		    	}
		    	}else{
    		        max_num = max(max(b_num,w_num), max_num);
		            w_num=1; b_num=1;
	    		}		
    		} 
	    }
    }
    printf("%d",max_num);
	return 0;
}

int max(int a, int b){
    return a > b ? a : b;
}

纯C写~~~
发表于 2017-03-30 16:08:49 回复(0)
n, *bw = open(0).read().split()
n = int(n)


def lamp(grid):
    B = [1 if i == 'B' else 0 for i in grid[0]]
    W = [1 if i == 'W' else 0 for i in grid[0]]
    m = max(max(B), max(W))
    for j in range(1, n):
        tb = [1 if i == 'B' else 0 for i in grid[j]]
        tw = [1 if i == 'W' else 0 for i in grid[j]]
        B = [B[i] + 1 if tb[i] == 1 else 0 for i in range(n)]
        W = [W[i] + 1 if tw[i] == 1 else 0 for i in range(n)]
        m = max(m, max(B), max(W))
    return m


print(max(lamp(bw), lamp(list(zip(*bw)))))  # 才发现题目只需要看列就行了。。。
python的特色zip不能不用,如果有numpy这题可以写的更优美点
编辑于 2020-07-21 17:32:34 回复(0)
各数组相同字符子串的最大长度
利用vector chess存取每次输入的字符串;在利用WB存取每一列的数据,然后判定连续的
最大相同字符串;提醒:能用vector尽量用vector,尽量不要用C语言里面的数组,会出来
很多你想不到的存储问题。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
int n, len=1,max_len=0;
vector<string> chess;
vector<char> WB;
string str,temp;
cin >> n;
for (int i = 0; i < n; i++)  //输入每行
{
cin >> str;
chess.push_back(str);
}
for (int k = 0; k < n; k++)
{
for (int m = 0; m < n; m++)、、提取每列,储存到WB
{
temp = chess[m];
WB.push_back(temp[k]);
}
for (int j = 0; j < WB.size() - 1; j++) 判断最大连续相同字符串
{
if (WB[j] == WB[j + 1])
{
len++;
max_len = max(max_len, len);//保证最大的那个,并存储
continue;
}
else
{
len = 1;
continue;
}
}
len = 1;
WB.clear(); //WB每次会存储新的一列,必须清空,空间可以保留
}
cout << max_len << endl;
return 0;

}
编辑于 2019-07-23 10:09:05 回复(0)
import sys


class Solution:
    def draw_color(self, matrix):
        col = 0
        max_count = 0
        while col < len(matrix):
            pre = ''
            tmp_count = 0
            for row in range(len(matrix)):
                if matrix[row][col] == pre:
                    tmp_count += 1
                    max_count = max([tmp_count, max_count])
                else:
                    pre = matrix[row][col]
                    max_count = max([tmp_count, max_count])
                    tmp_count = 1
            if max_count == len(matrix):
                print(max_count)
                return
            col += 1
        print(max_count)


if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    mat = list()
    for _ in range(n):
        mat.append(sys.stdin.readline().strip())
    solution = Solution()
    solution.draw_color(mat)

发表于 2018-07-12 14:50:36 回复(0)

import java.util.Scanner;

/*
* 相对简单的贪心
* */
public class BWTuban {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            String[] strings = new String[n];
            for (int i = 0; i < n; i++) {
                strings[i] = scanner.next();
            }
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
//                当前列,白色和黑色连续最大值
                int bCount = 0;
                int wCount = 0;
                for (int j = 0; j < n; j++) {
                    if(strings[j].charAt(i)=='B'){
                        int bTmp=1;
                        while(j+1<n&&strings[j+1].charAt(i)=='B'){
                            bTmp++;
                            j++;
                        }
//                        更新
                        bCount = Math.max(bCount,bTmp);
                    }
                    if(strings[j].charAt(i)=='W'){
                        int wTmp=1;
                        while(j+1<n&&strings[j+1].charAt(i)=='W'){
                            wTmp++;
                            j++;
                        }
                        wCount = Math.max(wCount,wTmp);
                    }
                }
//                更新
                max = Math.max(max,Math.max(bCount,wCount));
            }
            System.out.println(max);
        }
    }
}
发表于 2018-04-11 20:40:40 回复(0)
//判断当前字符是否与上一个last相等
//相等subMax++ 否则subMax置为1
//记得更新last

import java.util.Scanner;

public class Main1 {     public static int cal2(int[][] nums) {         int max=0;         for(int i=0; i<nums.length; i++) {             int last = nums[0][i];             int subMax=1;             for(int j=1; j<nums.length; j++) {                 if(last == nums[j][i]) {                     subMax+=1;                     if(subMax>max)    max=subMax;                 }else {                     subMax=1;                 }                 last = nums[j][i];             }         }         return max;     }     public static void main(String[] args) {         Scanner s = new Scanner(System.in);         int n = s.nextInt();         s.nextLine();         int[][] nums = new int[n][n];         for (int i = 0; i < n; i++) {             String str = s.nextLine();             for (int j = 0; j < n; j++) {                 char c = str.charAt(j);                 nums[i][j] = c;             }         }         System.out.println(cal2(nums));         s.close();     }
}





编辑于 2018-03-26 10:45:19 回复(0)
//注意count定义的位置,如果定义在for外层,则通过率只有80%

import java.util.Scanner;

public class test9 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String [] strings = new String[n];
        for(int i = 0;i < n;i++){
            strings[i] = scanner.next();
        }
        
        int max = Integer.MIN_VALUE;
        for(int j = 0;j < n;j++){
            int count = 1;
            for(int i = 0;i < n-1;i++){
                char temp = strings[i].charAt(j);
                if(strings[i+1].charAt(j) == temp){
                    count++;
                    max = Math.max(count, max);
                    //if(count > max){
                        
                        //System.out.println("the lie is " + j);
                    //}
                }
                else {
                    count = 1;
                }
            }
        }
        System.out.println(max);
    }

}


发表于 2018-03-03 20:39:57 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int maxLen = 0;
    string s;
    int n;
    cin>>n;
    vector<vector<char>> vvc(n,vector<char>(n));
    for(int i=0;i<n;i++) {
        cin>>s;
        for(int j=0;j<n;j++)
            vvc[i][j]=s[j];
    }
    for(int j=0;j<n;j++) {
        int curLen = 1;
        for(int i=1;i<n;i++)
            if(vvc[i][j]==vvc[i-1][j]) {
                if(++curLen>maxLen)
                    maxLen = curLen;
            }
            else
                curLen = 1;
    }
    cout<<maxLen;
}
发表于 2018-02-06 22:02:12 回复(0)
#include <iostream>
#include "list"
#include "vector"
#include <algorithm>
#include "math.h"
#include "map"
using namespace std;

int main()
{
    int line ;
    cin>>line;
    int max = 0;
    vector<vector<int>> map(line);
    for(int i = 0;i < line;++i)
    {
        string s;
        cin>>s;
        
        int temp = 1;
        map[i] = vector<int>(s.length());
        for(int j = 0;j < s.length() - 1;++j)
        {
            map[i][j] = s[j] == 'B'?1:-1;
            if(i != 0)
            {
                if(map[i - 1][j] * map[i][j] > 0)
                {
                    map[i][j] += map[i - 1][j];
                    
                }
                if(abs(map[i][j]) > max)
                    max = abs(map[i][j]);
            }
        }
    }
    
    cout<<max<<endl;
    return 0;
}
发表于 2018-01-17 10:44:31 回复(0)
using System;
namespace HelloWorldApplication
{
    class HelloWorld
    {
        static void Main(string[] args)
        {
            int num = 0;
            int.TryParse(Console.ReadLine(),out num);
            char[][] chars = new char[num][];
            for(int i=0;i<num;i++)
                chars[i] = Console.ReadLine().ToCharArray();
            int samenum = 1;
            for (int i = 0; i < num; i++)
            {
                int tmpsum = 1;
                char? lastchar=null;
                for (int j = 0; j < num; j++)
                {
                    if (chars[j][i]==lastchar)
                    {
                        tmpsum++;
                        if (samenum < tmpsum)
                            samenum = tmpsum;
                    }
                    else
                    {
                        lastchar=chars[j][i];
                        tmpsum=1;
                    }
                }
            }
            Console.WriteLine(samenum);
        }
    }
}
发表于 2018-01-06 03:00:48 回复(0)
#include <iostream>
using namespace std;

int update(int len) {
    static int maxLen = 0;
    if (len > maxLen) {
        maxLen = len;
    }
    return maxLen;
}

int main(int argc, const char * argv[]) {
    int n;
    cin>>n;
    char board[n][n];
    for (int i = 0; i < n; i++) {
        cin>>board[i];
    }
    for (int i = 0; i < n; i++) {
        int seriesLen = 1;
        for (int j = 0; j < n - 1; j++) {
            if (board[j][i] == board[j + 1][i]) {
                seriesLen++;
            } else {
                update(seriesLen);
                seriesLen = 1;
            }
        }
        if (seriesLen != 1) {
            update(seriesLen);
        }
    }
    cout<<update(0);
    return 0;
}
发表于 2017-10-19 19:16:12 回复(0)
# -*- coding:utf-8 -*-
n = int(raw_input())
s = [[] fori in range(n)]
fori in range(n):
    si = raw_input()
    forj in range(n):
        s[i].append(si[j])
 
#s = np.array(s)无numpy
ss = [[]fori in range(n)]
fori in range(n):
    forj in range(n):
        ss[i].append(s[j][i])
s = ss
 
 
#计算每一列的最长连续子串
counts = []
fori in range(n):
    a = 0
    counter = 1
    ci = s[i]
    ifa+1< n:
        forj in range(a+1,n):
            ifci[j] == ci[a]:
                counter += 1
                ifj == n-1:
                    a += counter
                    counts.append(counter)
                    break
            ifci[j] != ci[a]:
                counts.append(counter)
                a += counter
                counter = 1
print max(counts)

编辑于 2017-08-19 10:44:57 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
intmain(){
    intn;
    cin >> n;
    vector<string> v(n, " ");
    for(inti = 0; i < n; ++i){
        cin >> v[i];
    }
    //计算每一列'B'的个数
    intres = 0;
    for(inti = 0; i < n; ++i){
        intnum = 1;
        for(intj = 1; j < n; ++j){
            if(v[j][i] == v[j - 1][i]){
                num ++;
            }
            else{
                res = max(res, num);
                num = 1;
            }
        }
        res = max(res, num);
    }
    cout << res << endl;
}

发表于 2017-08-15 20:37:11 回复(0)
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<vector<char>> data;
	for (int i = 0;i<n;++i)
	{
		vector<char> vecTemp;
		for (int j = 0;j<n;++j)
		{	
			char temp;
			cin>>temp;
			vecTemp.push_back(temp);
		}
		data.push_back(vecTemp);
	}

	int out = 0;

	for (int j = 0;j<n;++j)
	{
		int maxBlack = -1;
		int maxWhite = -1;
		int blackCount = 0;
		int whiteCount = 0;

		for (int i = 0;i<n;++i)
		{
			if(data[i][j] == 'B'){
				blackCount++;
				maxWhite = max(maxWhite,whiteCount);
				whiteCount = 0;
			}
			else
			{
				whiteCount++;
				maxBlack = max(maxBlack,blackCount);
				blackCount = 0;
			}
		}
		maxBlack = max(maxBlack,blackCount);
		maxWhite = max(maxWhite,whiteCount);
		out = max(out,maxBlack);
		out = max(out,maxWhite);
	}
	cout<<out;
	return 0;
}

发表于 2017-08-12 11:41:33 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int count(vector<vector<char>> &p,int n){
    int numw=0,numb=0,maxw=0,maxb=0;
    char pre;
    if(p[0][n]=='W')
        numw++,pre='W';
    else
        numb++,pre='B';
    for(int i=1;i<p.size();i++){
        if(p[i][n]==pre){
            if(pre=='W'){
                numw++;
            }
            else{
                numb++;
            }
        }
        else{
            maxw=max(numw,maxw);
            maxb=max(numb,maxb);
            if(p[i][n]=='W'){
                numw=1;
                numb=0;
            }
            else{
                numw=0;
                numb=1;
            }
            pre=p[i][n];
        }
    }
	maxw = max(numw, maxw);
	maxb = max(numb, maxb);
    return max(maxb,maxw);
}

int main(){
    int n;
    cin>>n;
    vector<vector<char>> p;
    for(int i=0;i<n;i++){
        vector<char> t(n,'0');
        for(int j=0;j<n;j++){
            cin>>t[j];
        }
        p.push_back(t);
    }
    int maxc=0;
    for(int i=0;i<n;i++){
        maxc=max(maxc,count(p,i));
    }
    cout<<maxc<<endl;
    return 0;
}

发表于 2017-07-25 12:36:50 回复(0)