[BOJ 15671] 오델로

문제 출처 : https://www.acmicpc.net/problem/15671

 

풀이 :

문제 조건이 시키는대로 짜면 되는 문제입니다. (시뮬레이션...? 구현...?)

문제에 주어진 인풋대로 하면 무조건 정상적인 게임으로 성립이 됩니다.

 

조건

1. 처음 상태는 {{W,B},{B,W}}이다.

2. 돌은 반드시 포위하여 뒤집을 수 있는 곳에 놓아야 한다.

3. 돌을 뒤집을 수 없으면 상대 차례로 넘어간다.

 

2번 조건이 제일 중요한 조건으로 돌을 놓은 곳부터 2번조건을 성립시킬 수 있는 돌이 있는 곳까지 다 뒤집어 주되,

그 사이에 빈칸이 있으면 안됨을 고려해서 짜면 됩니다.

 

 

#include<stdio.h>
#include<stack>
using namespace std;
typedef pair<int, int> p;
 
int n, a, b, arr[7][7], dx[8] = { 1,-1,0,0,1,1,-1,-1 }, dy[8] = { 0,0,1,-1,1,-1,1,-1 }, bcnt, wcnt;
stack<p> s;
 
bool check(int y, int x, int w) {
    bool ret = false;
    arr[y][x] = w;
    for (int k = 0; k < 8; k++) {
        int ny = y + dy[k], nx = x + dx[k];
        if (ny == 0 || ny == n + 1 || nx == 0 || nx == n + 1 || !arr[ny][nx])continue;
        if (arr[ny][nx] != w) {
            int tmpy = ny + dy[k], tmpx = nx + dx[k];
            s.push({ ny,nx });
            for (; tmpy > 0 && tmpy < 7 && tmpx > 0 && tmpx < 7;) {
                if (!arr[tmpy][tmpx])break;
                if (arr[tmpy][tmpx] == w)
                {
                    while (!s.empty()) {
                        int cy = s.top().first, cx = s.top().second;
                        s.pop();
                        arr[cy][cx] = w;
                    }
                    ret = true;
                    break;
                }
                s.push({ tmpy,tmpx });
                tmpy += dy[k];
                tmpx += dx[k];
            }
            while (!s.empty())s.pop();
        }
    }
    return ret;
}
 
int main() {
    scanf("%d", &n);
    arr[3][3] = arr[4][4] = 1;
    arr[3][4] = arr[4][3] = 2;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a, &b);
        check(a, b, i % 2 + 1);
    }
    for (int i = 1; i <= 6; i++, printf("\n"))for (int j = 1; j <= 6; j++) {
        if (arr[i][j] == 0)printf(".");
        else if (arr[i][j] == 1) {
            printf("W");
            wcnt++;
        }
        else {
            printf("B");
            bcnt++;
        }
    }
    if (wcnt > bcnt)printf("White");
    else printf("Black");
}