235150301111015-Tugas8-Bonus XOXO

#include <iostream>
using namespace std;

const int N = 3;
const int MAX_WINS = 5;


struct GameState {
    char board[N][N];
    char currentPlayer;
};


void printBoard(char board[N][N]) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cout << board[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}


char checkWin(char board[N][N]) {
    for (int i = 0; i < N; ++i) {
        if (board[i][0] != ' ' && board[i][0] == board[i][1] && board[i][1] == board[i][2]) {
            return board[i][0];
        }
        if (board[0][i] != ' ' && board[0][i] == board[1][i] && board[1][i] == board[2][i]) {
            return board[0][i];
        }
    }

    if (board[0][0] != ' ' && board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
        return board[0][0];
    }
    if (board[0][2] != ' ' && board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
        return board[0][2];
    }
    return ' ';
}


bool dfs(GameState state, int depth, int& winCount, char wins[MAX_WINS][N][N]) {
    char winner = checkWin(state.board);
    if (winner != ' ') {
        cout << "Pemenang: " << winner << endl;
        printBoard(state.board);

        if (winCount < MAX_WINS) {
            for (int i = 0; i < N; ++i)
                for (int j = 0; j < N; ++j)
                    wins[winCount][i][j] = state.board[i][j];
            ++winCount;
        }

        return true;
    }
    if (depth == N * N) {
        return false;
    }
    bool foundWin = false;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (state.board[i][j] == ' ') {
                state.board[i][j] = state.currentPlayer;
                state.currentPlayer = (state.currentPlayer == 'X') ? 'O' : 'X';
                foundWin = dfs(state, depth + 1, winCount, wins) || foundWin;
                state.board[i][j] = ' ';
                state.currentPlayer = (state.currentPlayer == 'X') ? 'O' : 'X';
                if (winCount >= MAX_WINS) {
                    return true;
                }
            }
        }
    }
    return foundWin;
}

int main() {
    GameState initialState = {{{' ', ' ', ' '}, {' ', ' ', ' '}, {' ', ' ', ' '}}, 'X'};
    char wins[MAX_WINS][N][N];
    int winCount = 0;

    dfs(initialState, 0, winCount, wins);

    if (winCount < MAX_WINS) {
        cout << "Kurang dari " << MAX_WINS << " kemanangan yang ditemukan." << endl;
    } else {
        cout << "Menemukan " << MAX_WINS << " cara kemenangan:" << endl;
        for (int w = 0; w < winCount; ++w) {
            cout << "Metode Menang " << w + 1 << ":\n";
            printBoard(wins[w]);
        }
    }

    return 0;
}