커 리 어 컵 - 중간 난제 17.2

17.2 알고리즘 을 설계 하여 게이머 가 우물 글자 게임 을 이 겼 는 지 판단 한다.
해법:
만약 에 이 검사 에서 누군가가 우물 글자 게임 의 함 수 를 HasWon 으로 이 겼 는 지 확인한다 면 우 리 는 첫 번 째 단 계 는 면접 관 에 게 이 함수 가 한 번 만 호출 되 는 지, 아니면 여러 번 자주 호출 되 는 지 확인 해 야 한다.만약 여러 번 호출 된다 면, 우 리 는 예비 처 리 를 통 해 매우 빠 른 버 전 을 얻 을 수 있다.
방법 1: HasWon 함수 가 자주 호출 되 어야 한다 면
우물 글자 놀이 에 있어 서, 각 칸 이 비어 있 을 수 있 습 니 다. 나의 바둑 알 과 상대방 의 바둑 알 은 세 가지 가능성 이 있 습 니 다. 모두 39 가 있 습 니 다. = 19683 가지 가능 한 상태.우 리 는 모든 상 태 를 하나의 정수 로 바 꿀 수 있다. 예비 처리 할 때 이 상태 에서 우물 글자 게임 을 이 긴 사람 이 있 는 지 를 저장 할 수 있다. 검색 할 때마다 O (1) 시간 만 필요 하 다.예 를 들 어 각 칸 의 3 가지 상 태 는 0 (공), 1 (우리 측 바둑돌), 2 (상대방 바둑돌) 이 고 바둑판 은 왼쪽 에서 오른쪽으로, 위 에서 아래로 0 에서 8 로 순서대로 기록 하면 모든 상 태 는 3 진법 의 숫자 로 쓰 고 10 진법 으로 바 꾸 면 된다.예 를 들 어 아래 의 상태:

1 2 2

2 1 1

2 0 1

    :

122211201=1*3^8 + 2*3^7 +...+ 0*3^1 + 1*3^0

이때 계 산 된 정 수 를 어느 쪽 이 이 겼 거나 무승부 가 났 는 지 표시 하기 위해 서 는 19683 개의 배열 이 필요 하 다.
만약 누군가가 이 겼 는 지 안 이 겼 는 지 를 되 돌려 야 한다 면, 우리 측 인지 상대방 인지 알 필요 가 없다.그것 은 이 긴 사람 이 있 는 지 없 는 지 를 바 이 너 리 로 표시 할 수 있다.예 를 들 어 위의 상태 에서 1 을 이기 면 그 상 태 를 대응 하 는 위치 1 로 바 꿀 수 있다.누가 이 겼 는 지 알 고 싶다 면, 전처리 결 과 를 char 배열 로 저장 할 수 있다.
방법 2: HasWon 함수 가 한 번 만 호출 되 거나 적 으 면
만약 에 HasWon 함수 가 한 번 만 호출 되 거나 아주 적 게 호출 된다 면 우 리 는 결 과 를 미리 저장 할 필요 가 없고 직접 판단 하면 된다.단지 한 번 의 호출 을 위해 예비 처 리 를 하 는 것 은 가치 가 없다.
코드 는 다음 과 같 습 니 다. n * n 의 바둑판 이 이 기 는 지 여 부 를 판단 합 니 다. 즉, 같은 바둑판 이 한 줄 로 연결 되 는 것 입 니 다.
위 에서 아래로, 왼쪽 에서 오른쪽으로, 두 대각선.
C + + 구현 코드:

#include<vector>

#include<iostream>

using namespace std;



int convertBoardToInt(vector<vector<char> > &board)

{

    int factor=1;

    int sum=0;

    int i,j;

    int v;

    for(i=0; i<3; i++)

        for(j=0; j<3; j++)

        {

            v=0;

            if(board[i][j]=='X')

                v=1;

            if(board[i][j]=='O')

                v=2;

            sum+=v*factor;

            factor*=3;

        }

    return sum;

}



char hasWon(vector<vector<char> > &board)

{

    int i,j;

    int n=board.size();

    //     

    for(i=0; i<n; i++)

    {

        for(j=0; j<n-1; j++)

        {

            if(board[i][j]!=board[i][j+1])

                break;

        }

        if(j==n-1)

            return board[i][j];

    }

    //     

    for(j=0; j<n; j++)

    {

        for(i=0; i<n-1; i++)

        {

            if(board[i][j]!=board[i+1][j])

                break;

        }

        if(i==n-1)

            return board[i][j];

    }

    //      



    for(j=0; j<n-1; j++)

    {

        if(board[j][j]!=board[j+1][j+1])

            break;

    }

    if(j==n-1)

        return board[j][j];

    for(i=0; i<n-1; i++)

        if(board[i][n-i-1]!=board[i+1][n-i-2])

            break;

    if(i==n-1)

        return board[i][0];

    return board.empty();

}



int main()

{

    vector<vector<char> > vec={{'X','X','O'},{'X','X','O'},{'X','O','O'}};

    cout<<hasWon(vec)<<endl;

}