BAEKJOON 3085 - 사탕 게임

문제: https://www.acmicpc.net/problem/3085

문제

Little Ivan is bored at math class so he decided to play popular game called "Bomboni". At the beginning all fields of N×N square board contain candies (not necessarily of same color). When its his turn player should swap two neighbouring (up, down, left or right) candies of different color and then pick some sequence (in row or column) of same color candies which he will take and eat. 

Initial board configuration is given, help Ivan and write a program which will calculate maximal number of candies he can win in the first move. 

입력

In the first line of standard input there is one integer N (3 ≤ N ≤ 50), board dimensions. 

In next N lines initial board configuration is given, j-th character in i-th row denotes color of candy at square (i, j) : C (red), P (blue), Z (green), Y (yellow). It will always be possible to make first move. 

출력

In the first and only line of standard output print the maximal number of candies Ivan can win in the first move. 

예제 입력 1 

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 1 

4

힌트

swapping candies Y and C in 4th row Ivan gets sequence CCCC in first column.

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1 1번

• 데이터를 추가한 사람: 10jobss
• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: juhyun16

알고리즘 분류

• 브루트 포스

완전 탐색으로 풀 수 있는 쉬운 문제입니다.

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
 
//https://www.acmicpc.net/problem/3085
 
const int MAX = 50;
 
int countEatableCandy(int n, char candies[MAX][MAX])
{
    int maxCount = 1;
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < n; y++)
        {
            int curCount = 1;
            char startChar = candies[x][y];
 
            // to right
            for (int x2 = x + 1; x2 < n; x2++)
            {
                if (candies[x2][y] == startChar)
                {
                    curCount++;
                }
                else
                {
                    break;
                }
            }
            maxCount = max(maxCount, curCount);
 
            // to down
            curCount = 1;
            for (int y2 = y + 1; y2 < n; y2++)
            {
                if (candies[x][y2] == startChar)
                {
                    curCount++;
                }
                else
                {
                    break;
                }
            }
            maxCount = max(maxCount, curCount);
        }
    }
    return maxCount;
}
 
int main()
{
    int n;
    char candies[MAX][MAX];
    scanf("%d", &n);
    for (int x = 0; x < n; x++)
    {
        char row[MAX];
        scanf("%s", row);
        for (int j = 0; j < n; j++)
        {
            candies[x][j] = row[j];
        }
    }
 
    int maxCandy = 0;
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < n; y++)
        {
            char newCandies[MAX][MAX];
 
            // left
            if (x - 1 > 0)
            {
                memcpy(newCandies, candies, MAX * MAX * sizeof(char));
                newCandies[x - 1][y] = candies[x][y];
                newCandies[x][y] = candies[x - 1][y];
                maxCandy = max(maxCandy, countEatableCandy(n, newCandies));
            }
 
            // right
            if (x + 1 < n)
            {
                memcpy(newCandies, candies, MAX * MAX * sizeof(char));
                newCandies[x + 1][y] = candies[x][y];
                newCandies[x][y] = candies[x + 1][y];
                maxCandy = max(maxCandy, countEatableCandy(n, newCandies));
            }
 
            // down
            if (y - 1 > 0)
            {
                memcpy(newCandies, candies, MAX * MAX * sizeof(char));
                newCandies[x][y - 1] = candies[x][y];
                newCandies[x][y] = candies[x][y - 1];
                maxCandy = max(maxCandy, countEatableCandy(n, newCandies));
            }
 
            // up
            if (y + 1 < n)
            {
                memcpy(newCandies, candies, MAX * MAX * sizeof(char));
                newCandies[x][y + 1] = candies[x][y];
                newCandies[x][y] = candies[x][y + 1];
                maxCandy = max(maxCandy, countEatableCandy(n, newCandies));
            }
        }
    }
 
    printf("%d\n", maxCandy);
    return 0;
}