[백준] 8976번 - LAGNO / C++

문제

Lagno (also known as Reversi and Othello) is a board game for two players, one black and one white. The board is square, consisting of 8 rows and 8 columns.

In one move, the black player places a black piece into an empty square so that, in at least one of eight directions (up, down, left, right and the four diagonal directions), there is a row of white pieces between the newly placed piece and some other black piece. After placing, all white pieces between (in any direction) the newly placed black piece and pre-existing black pieces become black. 

Write a program that, for a given board layout, calculates the largest number of white pieces the black player can convert in one move. 

 

입력

The input contains eight lines, each consisting of exactly eight characters '.', 'B' or 'W'. The character '.' represents an empty square, the letter 'B' a square with a black piece, and the letter 'W' a square with a white piece. 

 

출력

Output the largest number of white pieces that black can convert in a single move. If there are no legal moves, output 0.

 

코드

#include <iostream>
#include <string>

using namespace std;

string board[8];
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 주어진 좌표가 범위 내인지 확인
bool in_range(int nr, int nc)
{
	if (nr < 0 || nr >= 8 || nc < 0 || nc >= 8)
		return false;
	return true;
}

// 뒤집을 수 있는 흰색돌의 개수를 구함
int get_number(int nr, int nc, int dir)
{
	int number = 0;
	bool flag = true;

	while (board[nr][nc] == 'W')
	{
		number++;		// 흰색돌의 개수를 셈
		nr += dr[dir];		// 다음 좌표로 이동
		nc += dc[dir];
		if (!in_range(nr, nc))	// 범위 밖이면 flag를 설정하고 반복 종료
		{
			flag = false;
			break;
		}
	}
	// 범위 내이면서 다음 돌이 검정돌이라면 흰색돌의 개수를 리턴
	if (flag && board[nr][nc] == 'B')
	{
		return number;
	}
	// 범위 밖이거나 빈칸이라면 0을 리턴
	return 0;
}

int main()
{
	int i, j, k;
	int nr, nc;
	int res, answer = 0;

	// 게임 보드 상태 저장
	for (i = 0; i < 8; i++)
	{
		cin >> board[i];
	}
	// 모든 좌표에 대하여
	for (i = 0; i < 8; i++)
	{
		for (j = 0; j < 8; j++)
		{
			// 빈칸이 아니라면 패스 (검정돌을 놓지 못함)
			if (board[i][j] != '.')
			{
				continue;
			}
			// 초기화
			res = 0;
			// 모든 방향에 대해 (상하좌우/대각선)
			for (k = 0; k < 8; k++)
			{
				nr = i + dr[k];
				nc = j + dc[k];
				// 범위밖이거나 흰색돌이 아니면 패스
				if (!in_range(nr, nc))
					continue;
				if (board[nr][nc] != 'W')
					continue;
				// 뒤집을 수 있는 흰색돌의 개수를 저장
				res += get_number(nr, nc, k);
			}
			// 최댓값을 갱신
			answer = max(answer, res);
		}
	}
	cout << answer << endl;
	return 0;
}

 

모든 빈칸에 대하여 검정돌을 놓는 경우를 확인했다. 빈칸에 검정돌을 놓은 후 모든 방향에 대해 흰색돌이 존재하는지 확인한다. 만약 존재한다면 현재 놓은 돌과 이미 있던 검정돌 사이에 뒤집을 수 있는 흰색돌이 얼마나 존재하는지 확인한다. 모두 확인했다면 확인된 최대 개수와 현재 돌을 놓아서 뒤집을 수 있는 흰색돌의 개수를 비교하여 최댓값을 갱신한다.

 

링크

8976번: LAGNO

inbdni/Baekjoon