/* Dasprog C - 2019
William Handi Wijaya
0087

Program untuk mencari jalan yang dapat dilalui oleh tikus (2)
dalam suatu labirin agar tikus mendapatkan keju (3).
(1) = jalan, (0) = tembok
(Input berasal dari stdin)
*/

#include <stdio.h>
#include <string.h>
#define limit 100

// Prototipe fungsi
int get_ukuran(void);
int get_maze(int soal[][limit]);
bool valid(int soal[][limit], int x, int y, bool visited[][limit]);
bool check_move(int soal[][limit], int x, int y, int hasil[][limit], bool visited[][limit]);
void print_arr(int arr[][limit]);

// Declarasikan variabel global
int size;
int start_x, start_y;
int end_x, end_y;

int main(void)
{
    // Dapatkan ukuran
    if (get_ukuran() != 0) return 1;

    // Deklarasikan array
    int soal[size][limit], hasil[size][limit];

    // Deklarasikan flag
    bool visited[size][limit];

    // Isi tiap array
    memset(hasil, 0, sizeof(int) * size * limit);
    memset(visited, false, sizeof(bool) * size * limit);

    // Dapatkan maze dari user input
    // Jika input invalid, stop program
    if (get_maze(soal) != 0) return 2;

    // Print check_move result
    // Jika solusi ada
    if (check_move(soal, start_x, start_y, hasil, visited))
    {
        printf("\nSolusi:\n");
        print_arr(hasil);
    }
    // Jika solusi tidak ada
    else
    {
        printf("\nSolusi tidak ada\n");
        return 3;
    }
    return 0;
}

// Function
int get_ukuran(void)
{
    // Prompt user untuk memberikan ukuran maze
    printf("Ukuran maze (jangan melampaui %d): ", limit);
    scanf("%d", &size);

    // Jika size is too big, stop program
    if (size > limit)
    {
        printf("Ukuran maze telah melampaui batas !\n");
        return 1;
    }
    return 0;
}

int get_maze(int soal[][limit])
{
    // Deklarasikan variabel penyimpan banyaknya tikus dan keju
    int count_2 = 0;
    int count_3 = 0;

    // Prompt user untuk memberikan maze layout
    printf("Input %dx%d maze ! (2 = tikus and 3 = keju)\n", size, size);
    // Untuk setiap column
    for (int y = 0; y < size; y++)
    {
        // Untuk setiap row
        for (int x = 0; x < size; x++)
        {
            // Simpan user input
            scanf("%d", &soal[x][y]);
            // Validate input
            if (soal[x][y] == 2 || soal[x][y] == 3)
            {
                // Dapatkan start koordinat
                if (soal[x][y] == 2)
                {
                    count_2++;
                    start_x = x;
                    start_y = y;
                }
                // Dapatkan stop koordinat
                else if (soal[x][y] == 3)
                {
                    count_3++;
                    end_x = x;
                    end_y = y;
                }
                // Jika tikus/keju lebih dari satu, stop program
                if (count_2 > 1 || count_3 > 1)
                {
                    printf("Terlalu banyak tikus/keju\n");
                    return 2;
                }
            }
            // Jika user input berada di luar range x (0 <= x <= 3), stop program
            else if (soal[x][y] != 0 && soal[x][y] != 1)
            {
                printf("Invalid Input\n");
                return 3;
            }
        }
    }
    // Jika tidak ada tikus/keju, stop program
    if (count_2 == 0 || count_3 == 0)
    {
        printf("Posisi tikus/keju tidak diketahui\n");
        return 4;
    }
    return 0;
}

// Cek validitas dari koordiat saat ini (dalam sumbu x dan y)
bool valid(int soal[][limit], int x, int y, bool visited[][limit])
{
    if (0 <= x && x <= size - 1 && 0 <= y && y <= size - 1 && soal[x][y] != 0 && visited[x][y] == false)
    {
        return true;
    }
    else return false;
}

// Dapatkan solusi
bool check_move(int soal[][limit], int x, int y, int hasil[][limit], bool visited[][limit])
{
    // Base case
    // Jika curr_coordinate = keju, stop loop
    if (x == end_x && y == end_y)
    {
        hasil[x][y] = soal[x][y];
        visited[x][y] = true;
        return true;
    }
    // Recursive case
    if (valid(soal, x, y, visited))
    {
        hasil[x][y] = soal[x][y];
        visited[x][y] = true;

        if (check_move(soal, x, y - 1, hasil, visited)) return true; // Check up
        if (check_move(soal, x, y + 1, hasil, visited)) return true; // Check down
        if (check_move(soal, x - 1, y, hasil, visited)) return true; // Check kiri
        if (check_move(soal, x + 1, y, hasil, visited)) return true; // Check kanan

        // Jika setiap check_move di atas salah, stop program
        hasil[x][y] = 0;
        return false;
    }
    else return false;
}

void print_arr(int arr[][limit])
{
    for (int y = 0; y < size; y++)
    {
        for (int x = 0; x < size; x++)
        {
            printf("%d ", arr[x][y]);
        }
        printf("\n");
    }
}