Table of Contents
Frog in Maze – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Frog in Maze HackerRank Solution
#include <bits/stdc++.h>
#define endl '\n'
#define double long double
using namespace std;
const int MAXN = (42);
const double eps = 1e-12;
vector<double> gauss(vector<vector<double>> &a)
{
int n = a.size(), m = a[0].size() - 1;
vector<int> where(m, -1);
for(int col = 0, row = 0; col < m && row < n; col++)
{
int sel = row;
for(int i = row; i < n; i++)
if(abs(a[i][col]) > abs(a[sel][col]))
sel = i;
if(abs(a[sel][col]) < eps) { where[col] = -1; continue; }
for(int i = col; i <= m; i++)
swap(a[sel][i], a[row][i]);
where[col] = row;
for(int i = 0; i < n; i++)
if(i != row)
{
if(abs(a[i][col]) < eps) continue;
double c = a[i][col] / a[row][col];
for(int j = 0; j <= m; j++)
a[i][j] -= c * a[row][j];
}
row++;
}
vector<double> ans(m, 0);
for(int i = 0; i < m; i++)
if(where[i] != -1)
ans[i] = a[where[i]][m] / a[where[i]][i];
for(int i = 0; i < n; i++)
{
double sum = a[i][m];
for(int j = 0; j < m; j++)
sum -= ans[j] * a[i][j];
if(abs(sum) > eps) return vector<double>();
}
return ans;
}
int n, m, k;
string a[MAXN];
int nxt_x[MAXN][MAXN], nxt_y[MAXN][MAXN];
void read()
{
cin >> n >> m >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
nxt_x[i][j] = i, nxt_y[i][j] = j;
for(int i = 0; i < k; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--; y1--; x2--; y2--;
nxt_x[x1][y1] = x2; nxt_y[x1][y1] = y2;
nxt_x[x2][y2] = x1; nxt_y[x2][y2] = y1;
}
}
int N;
int encode(int x, int y) { return x * m + y; }
int dirx[4] = {0, 0, 1, -1};
int diry[4] = {1, -1, 0, 0};
bool ok(int x, int y)
{
if(x >= n || y >= m || x < 0 || y < 0) return false;
return a[x][y] != '#';
}
void solve()
{
N = n * m;
vector<vector<double> > matr;
vector<double> zero(N + 1, 0);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(a[i][j] == '#') { matr.push_back(zero); continue; }
else if(a[i][j] == '*') { matr.push_back(zero), matr[matr.size() - 1][encode(i, j)] = 1; continue; }
else if(a[i][j] == '%') { matr.push_back(zero), matr[matr.size() - 1][encode(i, j)] = 1; matr[matr.size() - 1][N] = 1; continue; }
vector<int> adj;
for(int d = 0; d < 4; d++)
if(ok(i + dirx[d], j + diry[d]))
adj.push_back(encode(nxt_x[i + dirx[d]][j + diry[d]], nxt_y[i + dirx[d]][j + diry[d]]));
matr.push_back(zero);
matr[matr.size() - 1][encode(i, j)] = 1;
for(int v: adj)
matr[matr.size() - 1][v] = -((double)1 / (double)adj.size());
}
vector<double> ans = gauss(matr);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(a[i][j] == 'A')
{
cout << setprecision(9) << fixed << ans[encode(i, j)] << endl;
return;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
read();
solve();
return 0;
}
Java Frog in Maze HackerRank Solution
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
FrogInMaze solver = new FrogInMaze();
solver.solve(1, in, out);
out.close();
}
static class FrogInMaze {
public int[] dx = {-1, 0, 1, 0};
public int[] dy = {0, -1, 0, 1};
public int[][] ts;
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
char[][] grid = new char[n][m];
for (int i = 0; i < n; i++) {
grid[i] = in.next().toCharArray();
}
int[][][] neighbor = new int[n][m][];
ts = new int[k][4];
for (int i = 0; i < k; i++) {
for (int j = 0; j < 4; j++)
ts[i][j] = in.nextInt() - 1;
neighbor[ts[i][0]][ts[i][1]] = new int[]{ts[i][2], ts[i][3]};
neighbor[ts[i][2]][ts[i][3]] = new int[]{ts[i][0], ts[i][1]};
}
double[][] mat = new double[n * m][n * m + 1];
int sx = 0, sy = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mat[i * m + j][i * m + j] = 1;
if (grid[i][j] == '%') {
mat[i * m + j][n * m] = 1;
continue;
}
if (grid[i][j] == '*' || grid[i][j] == '#') {
mat[i * m + j][n * m] = 0;
continue;
}
if (grid[i][j] == 'A') {
sx = i;
sy = j;
}
int avail = 0;
for (int r = 0; r < 4; r++) {
int ni = i + dx[r], nj = j + dy[r];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] != '#') {
avail++;
}
}
for (int r = 0; r < 4; r++) {
int ni = i + dx[r], nj = j + dy[r];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] != '#') {
if (neighbor[ni][nj] != null) {
int[] x = neighbor[ni][nj];
ni = x[0];
nj = x[1];
}
mat[i * m + j][ni * m + nj] -= 1.0 / avail;
}
}
}
}
RowReduce.rref(mat);
for (int i = 0; i < n * m; i++) {
if (mat[i][sx * m + sy] > 1e-8) {
out.printf("%.10f\n", mat[i][n * m]);
return;
}
}
out.println(0);
}
}
static class RowReduce {
public static void rref(double[][] M) {
int row = M.length;
if (row == 0)
return;
int col = M[0].length;
int lead = 0;
for (int r = 0; r < row; r++) {
if (lead >= col)
return;
int k = r;
while (M[k][lead] == 0) {
k++;
if (k == row) {
k = r;
lead++;
if (lead == col)
return;
}
}
double[] temp = M[r];
M[r] = M[k];
M[k] = temp;
double lv = M[r][lead];
for (int j = 0; j < col; j++)
M[r][j] /= lv;
for (int i = 0; i < row; i++) {
if (i != r) {
lv = M[i][lead];
for (int j = 0; j < col; j++)
M[i][j] -= lv * M[r][j];
}
}
lead++;
}
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public String next() {
int c;
while (isSpaceChar(c = this.read())) {
;
}
StringBuilder result = new StringBuilder();
result.appendCodePoint(c);
while (!isSpaceChar(c = this.read())) {
result.appendCodePoint(c);
}
return result.toString();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void printf(String format, Object... objects) {
writer.printf(format, objects);
}
public void close() {
writer.close();
}
public void println(int i) {
writer.println(i);
}
}
}
Leave a comment below
