/* 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 file)
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

// Prototipe fungsi
int get_maze(int *soal);
void get_start(int x, int y, int tmp);
int valid_input(int tmp);
bool check_move(int *soal, int x, int y, int *hasil, bool *visited);
bool valid_pos(int *soal, int x, int y, bool *visited);
void print_arr(int *arr);

// Declarasikan variabel global
int count_2 = 0;
int count_3 = 0;
int size;
int besar;
FILE *inptr = NULL;
int start_x, start_y;
int end_x, end_y;

int main(void)
{
    // Buka file
    inptr = fopen("input.txt" , "r");

    // Dapatkan ukuran
    fscanf(inptr, "%d", &size);
    besar = size * size;

    // Deklarasikan array
    int *soal = malloc(sizeof(int) * besar);
    int *hasil = malloc(sizeof(int) * besar);

    // Deklarasikan flag
    bool *visited = malloc(sizeof(bool) * besar);

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

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

    // Jika ada solusi
    if (check_move(soal, start_x, start_y, hasil, visited))
    {
        printf("\nSolusi:\n");
        print_arr(hasil);
    }
    // Jika tidak ada solusi
    else
    {
        printf("\nTidak ada solusi\n");
        return 2;
    }
    fclose(inptr);
    free(soal);
    free(hasil);
    return 0;
}

int get_maze(int *soal)
{
    // Untuk setiap column
    for (int y = 0; y < size; y++)
    {
        // Untuk setiap row
        for (int x = 0; x < size; x++)
        {
            // Isi map
            fscanf(inptr, "%d", &soal[x + y * size]);
            int tmp = soal[x + y * size];

            // Validasi input
            get_start(x, y, tmp);
            if (valid_input(tmp) != 0) return 1;
        }
    }
    // Jika tidak ada keju/tikus, stop program
    if (count_2 == 0 || count_3 == 0)
    {
        printf("Posisi tikus/keju tidak diketahui\n");
        return 4;
    }
    return 0;
}

void get_start(int x, int y, int tmp)
{
    if (tmp == 2 || tmp == 3)
    {
        // Dapatkan start koordinat
        if (tmp == 2)
        {
            count_2++;
            start_x = x;
            start_y = y;
        }
        // Dapatkan stop koordinat
        else if (tmp == 3)
        {
            count_3++;
            end_x = x;
            end_y = y;
        }
    }
    return;
}

int valid_input(int tmp)
{
    // Jika tikus/keju lebih dari satu, stop program
    if (count_2 > 1 || count_3 > 1)
    {
        printf("Terlalu banyak tikus/keju\n");
        return 1;
    }
    // Jika user input berada di luar range x (0 <= x <= 3), stop program
    if (tmp < 0 || tmp > 3)
    {
        printf("Invalid Input\n");
        return 2;
    }
    else return 0;
}

// Dapatkan solution
bool check_move(int *soal, int x, int y, int *hasil, bool *visited)
{
    // Base case
    // Jika curr_coordinate = stop point, stop loop
    if (x == end_x && y == end_y)
    {
        *(hasil + x + y * size) = *(soal + x + y * size);
        *(visited + x + y * size) = true;
        return true;
    }
    // Recursive case
    if (valid_pos(soal, x, y, visited))
    {
        *(hasil + x + y * size) = *(soal + x + y * size);
        *(visited + x + y * size) = 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

        // if every check_move above is false, stop program
        *(hasil + x + y * size) = 0;
        return false;
    }
    else return false;
}

// Jika setiap check_move di atas salah, stop program
bool valid_pos(int *soal, int x, int y, bool *visited)
{
    if (0 <= x && x <= size - 1 && 0 <= y && y <= size - 1 && *(soal + x + y * size) != 0 && *(visited + x + y * size) == false)
    {
        return true;
    }
    else return false;
}

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