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("%d\n", 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;
}
0 Comments