HackerRank Huarongdao problem solution

In this HackerRank Huarongdao problem solution, Huarongdao is a well-known game in China. The purpose of this game is to move the Cao Cao block out of the board.

Acme is interested in this game, and he invents a similar game. There is a N*M board. Some blocks in this board are movable, while some are fixed. There is only one empty position. In one step, you can move a block to the empty position, and it will take you one second. The purpose of this game is to move the Cao Cao block to a given position. Acme wants to finish the game as fast as possible.

But he finds it hard, so he cheats sometimes. When he cheats, he spends K seconds picking a block and put it in an empty position. However, he is not allowed to pick the Cao Cao block out of the board.

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static int nRow, nCol;
  static int[][] board;

  static boolean valid(int row, int col) {
    return 0 <= row && row < nRow && 0 <= col && col < nCol && board[row][col] == 1;
  }

  static class Node {
    int row, col, len;

    Node() {};

    Node(int r, int c, int l) {
      row = r;
      col = c;
      len = l;
    }
  }

  static int k;
  static boolean[][] visited;
  static int[] dx = {-1, 1, 0, 0};
  static int[] dy = {0, 0, -1, 1};
  static Node[] q = new Node[50000];

  static void bfs(Node t, Node cc, int ret[]) {
      for (boolean[] visited1 : visited) {
          Arrays.fill(visited1, false);
      }

    int tail = 0;
    q[tail++] = t;
    visited[t.row][t.col] = true;

    for (int i = 0; i < 4; i++) {
      ret[i] = -2;
      int nx = cc.row + dx[i];
      int ny = cc.col + dy[i];
      if (t.row == nx && t.col == ny) {
        ret[i] = 0;
      }
      if (!valid(nx, ny)) {
        ret[i] = -1;
      }
    }

    int head = 0;
    while (head < tail) {
      Node tmp = q[head++];

      if (tmp.len == k - 1) {
        break;
      }

      for (int i = 0; i < 4; i++) {
        int nr = tmp.row + dx[i];
        int nc = tmp.col + dy[i];
        int len = tmp.len + 1;
        if (valid(nr, nc) && (nr != cc.row || nc != cc.col) && !visited[nr][nc]) {
          visited[nr][nc] = true;
          Node next = new Node(nr, nc, len);
          for (int j = 0; j < 4; j++) {
            int nx = cc.row + dx[j];
            int ny = cc.col + dy[j];
            if (nr == nx && ny == nc) {
              ret[j] = len;
              break;
            }
          }
          q[tail++] = next;
        }
      }
    }

    for (int i = 0; i < 4; i++) {
      if (ret[i] == -2) {
        ret[i] = k;
      }
    }
  }

  static int[][][][] dist;

  static void initdist() {
    for (int[][][] dist1 : dist) {
      for (int[][] dist2 : dist1) {
        for (int[] dist3 : dist2) {
          Arrays.fill(dist3, -1);
        }
      }
    }

    for (int i = 0; i < nRow; i++) {
      for (int j = 0; j < nCol; j++) {
        if (board[i][j] != 0) {
          for (int d = 0; d < 4; d++) {
            int emptyRow = i + dx[d];
            int emptyCol = j + dy[d];
            if (!valid(emptyRow, emptyCol)) continue;
            Node t = new Node(emptyRow, emptyCol, 0);
            Node cc = new Node(i, j, 0);
            bfs(t, cc, dist[i][j][d]);
          }
        }
      }
    }
  }

  static class Node2 {
    int row, col, dir;

    Node2() {};

    Node2(int r, int c, int d) {
      row = r;
      col = c;
      dir = d;
    }
  }

  static Node2 swapBlocks(Node2 cc) {
    int ndir = cc.dir <= 1 ? 1 - cc.dir : 5 - cc.dir;
    return new Node2(cc.row + dx[cc.dir], cc.col + dy[cc.dir], ndir);
  }

  static int[][][] dist2;
  static int[][][] cnt;
  static final int MAXLEN = 500000;
  static Node2[] q2 = new Node2[MAXLEN];

  static int spfa(Node cc, int[] start, Node target) {
    for (int[][] dist3 : dist2) {
      for (int[] dist4 : dist3) {
        Arrays.fill(dist4, -1);
      }
    }
    for (int[][] cnt1 : cnt) {
      for (int[] cnt2 : cnt1) {
        Arrays.fill(cnt2, 0);
      }
    }

    int tail = 0;
    for (int i = 0; i < 4; i++) {
      if (start[i] != -1) {
        int ex = cc.row + dx[i];
        int ey = cc.col + dy[i];
        if (valid(ex, ey)) {
          Node2 tmp = new Node2(cc.row, cc.col, i);
          dist2[cc.row][cc.col][i] = start[i];
          cnt[cc.row][cc.col][i]++;
          q2[tail++] = tmp;
        }
      }
    }

    int head = 0;
    while (head != tail) {
      Node2 tmp = q2[head];
      head = (head + 1) % MAXLEN;
      int tr = tmp.row;
      int tc = tmp.col;
      int td = tmp.dir;
      cnt[tr][tc][td]--;

      for (int i = 0; i < 4; i++) {
        if (i == td) {
            continue;
        }
        if (dist[tr][tc][td][i] == -1) {
            continue;
        }
        if (dist2[tr][tc][i] == -1
            || (dist2[tr][tc][i] > dist2[tr][tc][td] + dist[tr][tc][td][i])) {
          dist2[tr][tc][i] = dist2[tr][tc][td] + dist[tr][tc][td][i];
          if (cnt[tr][tc][i] == 0) {
            q2[tail] = new Node2(tr, tc, i);
            tail = (tail + 1) % MAXLEN;
            cnt[tr][tc][i]++;
          }
        }
      }

      Node2 swapped = swapBlocks(tmp);
      int r = swapped.row;
      int c = swapped.col;
      int d = swapped.dir;
      if (dist2[r][c][d] == -1 || (dist2[r][c][d] > dist2[tr][tc][td] + 1)) {
        dist2[r][c][d] = dist2[tr][tc][td] + 1;
        if (cnt[r][c][d] == 0) {
          q2[tail] = new Node2(r, c, d);
          tail = (tail + 1) % MAXLEN;
          cnt[r][c][d]++;
        }
      }
    }

    int ret = -1;
    for (int i = 0; i < 4; i++) {
      int val = dist2[target.row][target.col][i];
      if (val != -1 && (ret == -1 || val < ret)) {
          ret = val;
      }
    }

    return ret;
  }

  static class Query {
    int ex;
    int ey;
    int sx;
    int sy;
    int tx;
    int ty;
    public Query(int ex, int ey, int sx, int sy, int tx, int ty) {
      this.ex = ex;
      this.ey = ey;
      this.sx = sx;
      this.sy = sy;
      this.tx = tx;
      this.ty = ty;
    }
    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + ex;
      result = prime * result + ey;
      result = prime * result + sx;
      result = prime * result + sy;
      result = prime * result + tx;
      result = prime * result + ty;
      return result;
    }
    @Override
    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      Query other = (Query) obj;
      if (ex != other.ex) return false;
      if (ey != other.ey) return false;
      if (sx != other.sx) return false;
      if (sy != other.sy) return false;
      if (tx != other.tx) return false;
      if (ty != other.ty) return false;
      return true;
    }
    
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    nRow = Integer.parseInt(st.nextToken());
    nCol = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    board = new int[nRow][nCol];
    for (int i = 0; i < nRow; i++) {
        st = new StringTokenizer(br.readLine());
      for (int j = 0; j < nCol; j++) {
        board[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    visited = new boolean[nRow][nCol];
    dist = new int[nRow][nCol][4][4];
    dist2 = new int[nRow][nCol][4];
    cnt = new int[nRow][nCol][4];
    initdist();

    Map<Query, Integer> map = new HashMap<>();
    while (q-- > 0) {
      st = new StringTokenizer(br.readLine());
      int ex = Integer.parseInt(st.nextToken()) - 1;
      int ey = Integer.parseInt(st.nextToken()) - 1;
      int sx = Integer.parseInt(st.nextToken()) - 1;
      int sy = Integer.parseInt(st.nextToken()) - 1;
      int tx = Integer.parseInt(st.nextToken()) - 1;
      int ty = Integer.parseInt(st.nextToken()) - 1;

      Query query = new Query(ex, ey, sx, sy, tx, ty);
      if (map.containsKey(query)) {
        bw.write(String.valueOf(map.get(query)));
        bw.newLine();
        continue;
      }

      Node t = new Node(ex, ey, 0);
      Node cc = new Node(sx, sy, 0);
      int[] ret = new int[4];
      bfs(t, cc, ret);

      Node target = new Node(tx, ty, 0);
      int result = spfa(cc, ret, target);
      bw.write(String.valueOf(result));
      bw.newLine();

      map.put(query, result);
    }

    bw.close();
    br.close();
  }
}

Problem solution in C++.

#include<cstdio>
#include<cstring>
using namespace std;

int nRow, nCol, k;

int board[200][200];
int dist[200][200][4][4];

const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = { 0, 0, -1, 1 };

bool valid(int row, int col)
{
    return 0 <= row && row < nRow && 0 <= col && col < nCol && board[row][col] == 1;
}

struct Node
{
    int row, col, len;
    Node() {};
    Node(int r, int c, int l) : row(r), col(c), len(l) {};
};

Node q[50000];
bool visited[200][200];

void bfs(Node t, Node cc, int ret[])
{
    memset(visited, false, sizeof(visited));

    int head = 0, tail = 0;
    q[tail++] = t;
    visited[t.row][t.col] = true;

    for (int i = 0; i < 4; i++)
    {
        ret[i] = -2;
        int nx = cc.row + dx[i];
        int ny = cc.col + dy[i];
        if (t.row == nx && t.col == ny) ret[i] = 0;
        if (!valid(nx, ny)) ret[i] = -1;
    }

    while (head < tail)
    {
        Node tmp = q[head++];

        if (tmp.len == k - 1)
            break;

        for (int i = 0; i < 4; i++)
        {
            int nr = tmp.row + dx[i];
            int nc = tmp.col + dy[i];
            int len = tmp.len + 1;
            if (valid(nr, nc) && (nr != cc.row || nc != cc.col) && !visited[nr][nc])
            {
                visited[nr][nc] = true;
                Node next(nr, nc, len);
                for (int j = 0; j < 4; j++)
                {
                    int nx = cc.row + dx[j];
                    int ny = cc.col + dy[j];
                    if (nr == nx && ny == nc)
                    {
                        ret[j] = len;
                        break;
                    }
                }
                q[tail++] = next;
            }
        }
    }

    for (int i = 0; i < 4; i++)
        if (ret[i] == -2)
            ret[i] = k;
}

void initdist()
{
    memset(dist, -1, sizeof(dist));
    for (int i = 0; i < nRow; i++)
        for (int j = 0; j < nCol; j++)
            if (board[i][j] != 0)
                for (int d = 0; d < 4; d++)
                {
                    int emptyRow = i + dx[d];
                    int emptyCol = j + dy[d];
                    if (!valid(emptyRow, emptyCol)) continue;
                    Node t(emptyRow, emptyCol, 0);
                    Node cc(i, j, 0);
                    bfs(t, cc, dist[i][j][d]);
                }
}

int dist2[200][200][4];
int cnt[200][200][4];

struct Node2
{
    int row, col, dir;
    Node2() {};
    Node2(int r, int c, int d) : row(r), col(c), dir(d) {};
};

Node2 swapBlocks(Node2 cc)
{
    int cc_nr = cc.row + dx[cc.dir];
    int cc_nc = cc.col + dy[cc.dir];
    int ndir;
    if (cc.dir <= 1) ndir = 1 - cc.dir;
    else ndir = 5 - cc.dir;
    Node2 ret(cc_nr, cc_nc, ndir);
    return ret;
}

const int MAXLEN = 500000;
Node2 q2[MAXLEN];

void spfa(Node cc, int start[4], Node target)
{
    memset(dist2, -1, sizeof(dist2));
    memset(cnt, 0, sizeof(cnt));

    int head = 0, tail = 0;
    for (int i = 0; i < 4; i++)
        if (start[i] != -1)
        {
            int ex = cc.row + dx[i];
            int ey = cc.col + dy[i];
            if (valid(ex, ey))
            {
                Node2 tmp(cc.row, cc.col, i);
                dist2[cc.row][cc.col][i] = start[i];
                cnt[cc.row][cc.col][i]++;
                q2[tail++] = tmp;
            }
        }

    while (head != tail)
    {
        Node2 tmp = q2[head];
        head = (head + 1) % MAXLEN;
        int tr = tmp.row, tc = tmp.col, td = tmp.dir;
        cnt[tr][tc][td]--;

        for (int i = 0; i < 4; i++)
        {
            if (i == td) continue;
            if (dist[tr][tc][td][i] == -1) continue;
            if (dist2[tr][tc][i] == -1 || (dist2[tr][tc][i] > dist2[tr][tc][td] + dist[tr][tc][td][i]))
            {
                dist2[tr][tc][i] = dist2[tr][tc][td] + dist[tr][tc][td][i];
                if (cnt[tr][tc][i] == 0)
                {
                    q2[tail] = Node2(tr, tc, i);
                    tail = (tail + 1) % MAXLEN;
                    cnt[tr][tc][i]++;
                }
            }
        }

        Node2 swapped = swapBlocks(tmp);
        int r = swapped.row, c = swapped.col, d = swapped.dir;
        if (dist2[r][c][d] == -1 || (dist2[r][c][d] > dist2[tr][tc][td] + 1))
        {
            dist2[r][c][d] = dist2[tr][tc][td] + 1;
            if (cnt[r][c][d] == 0)
            {
                q2[tail] = Node2(r, c, d);
                tail = (tail + 1) % MAXLEN;
                cnt[r][c][d]++;
            }
        }
    }

    int ret = -1;
    for (int i = 0; i < 4; i++)
    {
        int val = dist2[target.row][target.col][i];
        if (val != -1 && (ret == -1 || val < ret))
            ret = val;
    }

    printf("%dn", ret);
}

int main()
{
    int q;
    scanf("%d%d%d%d", &nRow, &nCol, &k, &q);
    for (int i = 0; i < nRow; i++)
        for (int j = 0; j < nCol; j++)
            scanf("%d", &board[i][j]);
    initdist();
    while (q--)
    {
        int ex, ey, sx, sy, tx, ty;
        scanf("%d%d%d%d%d%d", &ex, &ey, &sx, &sy, &tx, &ty);
        ex--, ey--, sx--, sy--, tx--, ty--;

        Node t(ex, ey, 0);
        Node cc(sx, sy, 0);
        Node target(tx, ty, 0);
        int ret[4];
        bfs(t, cc, ret);

        spfa(cc, ret, target);
    }
    return 0;
}