涂棋盘

2017-04-25  本文已影响0人  RobotBerry

问题描述

小易有一块n*n的棋盘,棋盘的每一个格子都为黑色或者白色,小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画,帮助小易算算他会涂画多少个棋格。

输入描述

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

输出描述

输出小易会涂画的区域大小

输入例子

3
BWW
BBB
BWB

输出例子

3

分析

遍历所有棋盘行即可,维护三个连续相同颜色棋盘格数量的最大值:
1.棋盘全局最大值
2.每一行全局最大值
3.每一行局部最大值

note

输入的每一行后面都有一个'\n',需要scanf("%c")处理掉,也可以使用string的getline方法从cin标准输入流中获取行数据。

代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<vector<char>> board(n, vector<char>(n));

    char c;
    scanf("%c", &c);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%c", &c);
            board[i][j] = c;
        }
        scanf("%c", &c);
    }

    int maxArea = 0;
    for (int j = 0; j < n; j++)
    {
        int localArea = 1, globalArea = 1;
        for (int i = 1; i < n; i++)
        {
            localArea = board[i][j] == board[i - 1][j] ? localArea + 1 : 1;
            globalArea = max(globalArea, localArea);
        }
        maxArea = max(maxArea, globalArea);
    }

    printf("%d\n", maxArea);

    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读