// 1368. Minimum Cost to Make at Least One Valid Path in a Grid
#include "leetcode.h"

/*
 * given an 'm x n' grid. each cell of the grid has a sign pointing to the next
 * cell you shhould visit if you are currently in this cell. notice that there
 * could be some signs on the cells of the grid that point outside the grid. you
 * will initially start at the upper left cell '(0, 0)'. a valid path in the
 * grid is a path that starts from the uppper left cell '(0, 0)' and ends at the
 * bbbottom right cell '(m - 1, n - 1)' following the signs on the grid. the
 * valid path does not have to bbe the shortest. return the minimum cost to make
 * the grid have at least one valid path
 */

struct node {
  int state[2];
  int moves;
};

struct queue {
  struct node data[10000];
  int front, rear;
};

void queue_init(struct queue *obj) {
  obj->front = -1;
  obj->rear = -1;
}

bool queue_empty(struct queue *obj) {
  return obj->front == -1 && obj->rear == -1;
}

void queue_push(struct queue *obj, int *state, int moves) {
  if (queue_empty(obj)) {
    obj->front = 0;
    obj->rear = 0;
  } else
    obj->rear = (obj->rear + 1) % 10000;
  obj->data[obj->rear].state[0] = state[0];
  obj->data[obj->rear].state[1] = state[1];
  obj->data[obj->rear].moves = moves;
}

struct node queue_pop(struct queue *obj) {
  struct node n = obj->data[obj->front];
  if (obj->front == obj->rear) {
    obj->front = -1;
    obj->rear = -1;
  } else
    obj->front = (obj->front + 1) % 10000;
  return n;
}

int minCost(int **grid, int gridSize, int *gridColSize) {
  int n = gridSize, m = *gridColSize, min = INT_MAX;
  int vis[100][100] = {0};
  int **dp = (int **)malloc((n + 1) * sizeof(int *));
  for (int i = 0; i < n + 1; i++)
    dp[i] = (int *)malloc((m + 1) * sizeof(int));
  for (int i = 0; i < n + 1; i++)
    for (int j = 0; j < m + 1; j++)
      dp[i][j] = -1;
  struct queue q;
  queue_init(&q);
  int init_state[2] = {0, 0};
  queue_push(&q, init_state, 0);
  dp[0][0] = 0;
  while (!queue_empty(&q)) {
    struct node curr = queue_pop(&q);
    int x = curr.state[0], y = curr.state[1];
    int dir[5][2] = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int i = 1; i < 5; i++) {
      int curr_move = 0, next[2];
      if (grid[x][y] != i)
        curr_move = 1;
      next[0] = x + dir[i][0];
      next[1] = y + dir[i][1];
      int next_move = curr.moves + curr_move;
      if (next[0] == n && next[1] == m && min < next_move)
        min = next_move;
      if (next[0] >= 0 && next[1] >= 0 && next[0] < n && next[1] < m &&
          (!vis[next[0]][next[1]] || dp[next[0]][next[1]] > next_move)) {
        dp[next[0]][next[1]] = next_move;
        vis[next[0]][next[1]] = 1;
        queue_push(&q, next, next_move);
      }
    }
  }
  int ans = dp[n - 1][m - 1];
  for (int i = 0; i < n + 1; i++)
    free(dp[i]);
  free(dp);
  return ans;
}

int main() {
  int g1i[4][4] = {{1, 1, 1, 1}, {2, 2, 2, 2}, {1, 1, 1, 1}, {2, 2, 2, 2}};
  int g2i[3][3] = {{1, 1, 3}, {3, 2, 2}, {1, 1, 4}};
  int g3i[2][2] = {{1, 2}, {4, 3}};
  struct two_d_arr g1, g2, g3;
  two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
  two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
  two_d_arr_init(&g3, ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i);
  printf("%d\n", minCost(g1.arr, g1.row_size, g1.col_size)); // expect: 3
  printf("%d\n", minCost(g2.arr, g2.row_size, g2.col_size)); // expect: 0
  printf("%d\n", minCost(g3.arr, g3.row_size, g3.col_size)); // expect: 1
  two_d_arr_free(&g1);
  two_d_arr_free(&g2);
  two_d_arr_free(&g3);
}