In this HackerRank Coin on the Table problem solution You have a rectangular board consisting of n rows, numbered from 1 to n, and m columns, numbered from 1 to m. The top left is (1,1) and the bottom right is (n,m). Initially - at time 0 - there is a coin on the top-left cell of your board. When the coin reaches a cell that has the letter '*', it will stay there permanently. When you punch on your board, your timer starts and the coin moves between cells. Before starting the game, you can make operations to change the board, such that you are sure that at or before time k the coin will reach the cell having the letter '*'. In each operation, you can select a cell with some letter other than '*' and change the letter to 'U', 'L', 'R', or 'D'. You need to carry out as few operations as possible in order to achieve your goal. Your task is to find the minimum number of operations.
Problem solution in Python.
#!/bin/python3
import os
import sys
from collections import deque
from itertools import product
def coinOnTheTable(m, k, board):
m = len(board)
n = len(board[0])
def is_inside(x, y):
return 0 <= x < m and 0 <= y < n
distances = {}
q = deque()
q.append(((0, 0, 0), 0))
while len(q) > 0:
(z, i, j), d = q.pop()
if not is_inside(i, j) or d > k:
continue
if (z, i, j) in distances:
continue
distances[(z, i, j)] = d
if board[i][j] == '*':
continue
q.append(((z + int(board[i][j] != 'U'), i - 1, j), d + 1))
q.append(((z + int(board[i][j] != 'D'), i + 1, j), d + 1))
q.append(((z + int(board[i][j] != 'L'), i, j - 1), d + 1))
q.append(((z + int(board[i][j] != 'R'), i, j + 1), d + 1))
special_i, special_j = next((i, j) for i, j in product(range(m), range(n))
if board[i][j] == '*')
for z in range(k + 1):
state = (z, special_i, special_j)
if state in distances and distances[state] <= k:
return z
return -1
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
board = []
for _ in range(n):
board_item = input()
board.append(board_item)
result = coinOnTheTable(m, k, board)
fptr.write(str(result) + '\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
char input[][] = new char[51][51];
int dp[][][] = new int[1001][51][51];
String line;
int N, M, K;
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
M = scanner.nextInt();
K = scanner.nextInt();
scanner.nextLine();
int finalRow = 0, finalColumn = 0;
for (int i = 0; i < N; i++) {
line = scanner.nextLine();
for (int j = 0; j < M; j++) {
input[i][j] = line.charAt(j);
if (input[i][j] == '*') {
finalRow = i;
finalColumn = j;
}
}
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
dp[0][i][j] = (i == finalRow && j == finalColumn) ? 0 : Integer.MAX_VALUE;
for (int k = 1; k <= K; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int min = Integer.MAX_VALUE;
dp[k][i][j] = dp[k - 1][i][j];
if (i - 1 >= 0)
min = Math.min(sumInfinite(dp[k - 1][i - 1][j], input[i][j] == 'U' ? 0 : 1), min);
if (i + 1 < N)
min = Math.min(sumInfinite(dp[k - 1][i + 1][j], input[i][j] == 'D' ? 0 : 1), min);
if (j - 1 >= 0)
min = Math.min(sumInfinite(dp[k - 1][i][j - 1], input[i][j] == 'L' ? 0 : 1), min);
if (j + 1 < M)
min = Math.min(sumInfinite(dp[k - 1][i][j + 1], input[i][j] == 'R' ? 0 : 1), min);
dp[k][i][j] = Math.min(dp[k][i][j], min);
}
}
}
System.out.print(dp[K][0][0] == Integer.MAX_VALUE ? "-1" : dp[K][0][0]);
}
public static int sumInfinite(int a, int b) {
return (a == Integer.MAX_VALUE || b == Integer.MAX_VALUE) ? Integer.MAX_VALUE : (a + b);
}
}Problem solution in C++.
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define MAXN 50
#define MAXM 50
#define INF 1000000
int N, M, K, ti, tj;
string board[MAXN];
int p[MAXN][MAXM];
void dfs(int i, int j, int k, int c) {
if (i >= 0 && j >= 0 && i < N && j < M && c < p[i][j] && k <= K) {
p[i][j] = c;
dfs(i - 1, j, k + 1, c + !(board[i][j] == 'U'));
dfs(i, j - 1, k + 1, c + !(board[i][j] == 'L'));
dfs(i + 1, j, k + 1, c + !(board[i][j] == 'D'));
dfs(i, j + 1, k + 1, c + !(board[i][j] == 'R'));
}
}
int getMinOperations() {
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXM; j++)
p[i][j] = INF;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (board[i][j] == '*') {
ti = i;
tj = j;
}
dfs(0, 0, 0, 0);
return (p[ti][tj] == INF ? -1 : p[ti][tj]);
}
int main() {
cin >> N >> M >> K;
for (int i = 0; i < N; i++)
cin >> board[i];
cout << getMinOperations() << endl;
return 0;
}Problem solution in C.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void update(int t, int i, int j, int N, int M, int K, int changes[][51], char table[][51]) {
int add = 1;
if(i>1) {
if(table[i-1][j]=='D') add = 0;
if(changes[i][j]+add<changes[i-1][j]) {
changes[i-1][j] = changes[i][j] + add;
if(t<K-1)update(t+1,i-1,j,N,M,K,changes,table);
}
}
add = 1;
if(i<N) {
if(table[i+1][j]=='U') add = 0;
if(changes[i][j]+add<changes[i+1][j]) {
changes[i+1][j] = changes[i][j] + add;
if(t<K-1)update(t+1,i+1,j,N,M,K,changes,table);
}
}
add = 1;
if(j>1) {
if(table[i][j-1]=='R') add = 0;
if(changes[i][j]+add<changes[i][j-1]) {
changes[i][j-1] = changes[i][j] + add;
if(t<K-1)update(t+1,i,j-1,N,M,K,changes,table);
}
}
add = 1;
if(j<M) {
if(table[i][j+1]=='L') add=0;
if(changes[i][j]+add<changes[i][j+1]) {
changes[i][j+1] = changes[i][j] + add;
if(t<K-1)update(t+1,i,j+1,N,M,K,changes,table);
}
}
return;
}
int main() {
char c, table[51][51];
int N,M,K,rs,cs,changes[51][51];
scanf("%d %d %d",&N,&M,&K);
scanf("%c",&c);
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
scanf("%c",&c);
table[i+1][j+1] = c;
if(c=='*') {
rs = i+1;
cs = j+1;
}
}
scanf("%c",&c);
}
if(cs+rs-2>K) { //destination too far away
printf("-1\n");
return 0;
}
for(int i=1;i<=N;i++) {
for(int j=1;j<=M;j++) {
changes[i][j] = abs(i-rs)+abs(j-cs)+1;
}
}
changes[rs][cs]=0;
update(0,rs,cs,N,M,K,changes,table);
printf("%d\n",changes[1][1]);
return 0;
}
0 Comments