HackerRank Frog in Maze Problem Solution

In this post, we will solve HackerRank Frog in Maze Problem Solution.

Alef the Frog is in an m x n two-dimensional maze represented as a table. The maze has the following characteristics:

Each cell can be free or can contain an obstacle, an exit, or a mine.
Any two cells in the table considered adjacent if they share a side.
The maze is surrounded by a solid wall made of obstacles.
Some pairs of free cells are connected by a bidirectional tunnel.

When Alef is in any cell, he can randomly and with equal probability choose to move into one of the adjacent cells that don’t contain an obstacle in it. If this cell contains a mine, the mine explodes and Alef dies. If this cell contains an exit, then Alef escapes the maze.

When Alef lands on a cell with an entrance to a tunnel, he is immediately transported through the tunnel and is thrown into the cell at the other end of the tunnel. Thereafter, he won’t fall again, and will now randomly move to one of the adjacent cells again. (He could possibly fall in the same tunnel later.)

It’s possible for Alef to get stuck in the maze in the case when the cell in which he was thrown into from a tunnel is surrounded by obstacles on all sides.

Your task is to write a program which calculates and prints a probability that Alef escapes the maze.

Input Format
The first line contains three space-separated integers n. m and k denoting the dimensions of
the maze and the number of bidirectional tunnels.
The next n lines describe the maze. The i’th line contains a string of length m denoting the i ‘th row of the maze. The meaning of each character is as follows:

denotes an obstacle
A denotes a free cell where Alef is initially in.
denotes a cell with a mine.
% denotes a cell with an exit.
o denotes a free cell (which may contain an entrance to a tunnel).

The next & lines describe the tunnels. The i’th line contains four space-separated integers i1, J1, i2, j2. Here, (i1, J1) and (i2, j2) denote the coordinates of both entrances of the tunnel.
(i, j) denotes the row and column number, respectively.

Output Format

Print one real number denoting the probability that Alef escapes the maze. Your answer will be considered to be correct if its (absolute) difference from the true answer is not greater than 10 power -6.

Sample Input 0

3 6 1
###*OO
O#OA%O
###*OO
2 3 2 1

Sample Output 0

0.25

Explanation 0

The following depicts this sample case:

In this case, Alef will randomly choose one of four adjacent cells. If he goes up or down, he will explode and die. If he goes right, he will escape. If he goes left, he will go through a tunnel and get stuck in cell (2, 1). So the probability of Alef escaping is 1/4.

HackerRank Frog in Maze Problem Solution

Frog in Maze C++ Solution

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

int main() {
	int H; int W; int K;
	while (~scanf("%d%d%d", &H, &W, &K)) {
		vector<string> maze(H);
		rep(i, H) {
			char buf[101];
			scanf("%s", buf);
			maze[i] = buf;
		}
		vector<int> tunnel(H * W, -1);
		rep(i, K) {
			int y1; int x1; int y2; int x2;
			scanf("%d%d%d%d", &y1, &x1, &y2, &x2), -- y1, -- x1, -- y2, -- x2;
			int u = y1 * W + x1, v = y2 * W + x2;
			tunnel[u] = v;
			tunnel[v] = u;
		}
		vector<vector<pair<int, double>>> gw(H * W);
		rep(i, H) rep(j, W) {
			int u = i * W + j;
			if (!strchr("#*%", maze[i][j])) {
				static const int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
				for (int d = 0; d < 4; ++ d) {
					int yy = i + dy[d], xx = j + dx[d];
					if (yy < 0 || yy >= H || xx < 0 || xx >= W) continue;
					if (maze[yy][xx] == '#') continue;
					int v = yy * W + xx;
					if (tunnel[v] != -1)
						v = tunnel[v];
					gw[u].emplace_back(v, 1.);
				}
			}
			if (gw[u].empty()) {
				gw[u].emplace_back(u, 1.);
			} else {
				for(auto &p : gw[u])
					p.second /= (int)gw[u].size();
			}
		}
		//(1 - A)^{-1} c
		typedef double Num;
		vector<vector<Num>> A(H * W, vector<Num>(H * W)), B = A;
		rep(u, H * W) for (auto e : gw[u])
			A[u][e.first] += e.second;
		rep(iter, 20) {
			rep(i, H * W) rep(j, H * W) {
				Num x = 0;
				rep(k, H * W)
					x += A[i][k] * A[k][j];
				if (x < 1e-20)
					x = 0;
				B[i][j] = x;
			}
			A.swap(B);
		}
		double ans = 0;
		rep(i, H) rep(j, W) if (maze[i][j] == 'A')
			rep(k, H) rep(l, W) if(maze[k][l] == '%')
				ans += A[i * W + j][k * W + l];
		printf("%.10f\n", ans);
	}
	return 0;
}

Frog in Maze Java8 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);
        }

    }
}

Frog in Maze Java7 Solution


import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class D {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), m = ni(), nt = ni();
		char[][] map = nm(n,m);
		int[][] portal = new int[n][m];
		for(int i = 0;i < n;i++)Arrays.fill(portal[i], -1);
		int[][] ts = new int[2*nt][];
		for(int i = 0;i < 2*nt;i++){
			ts[i] = na(2);
			for(int j = 0;j < 2;j++)ts[i][j]--;
			portal[ts[i][0]][ts[i][1]] = i;
		}
		int[] dr = { 1, 0, -1, 0 };
		int[] dc = { 0, 1, 0, -1 };
		double[][] M = new double[n*m][n*m];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(map[i][j] != '#' && map[i][j] != '*' && map[i][j] != '%'){
					int cango = 0;
					for(int k = 0;k < 4;k++){
						int ni = i + dr[k], nj = j + dc[k];
						if(ni >= 0 && ni < n && nj >= 0 && nj < m){
							if(map[ni][nj] != '#'){
								cango++;
								if(portal[ni][nj] >= 0){
									int to = portal[ni][nj]^1;
									M[ts[to][0]*m+ts[to][1]][i*m+j] += 1;
								}else{
									M[ni*m+nj][i*m+j] += 1;
								}
							}
						}
					}
					if(cango == 0){
						M[i*m+j][i*m+j] += 1;
					}else{
						for(int k = 0;k < n*m;k++){
							M[k][i*m+j] /= cango;
						}
					}
				}else{
					M[i*m+j][i*m+j] += 1;
				}
			}
		}
		int sr = -1, sc = -1;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(map[i][j] == 'A'){
					sr = i; sc = j;
				}
			}
		}
		double[] v = new double[n*m];
		v[sr*m+sc] = 1;
		double[] inf = INF(M, v);
		double ret = 0;
		double all = 0;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				all += inf[i*m+j];
				if(map[i][j] == '%'){
					ret += inf[i*m+j];
				}
			}
		}
		
		out.printf("%.14f\n", ret/all);
	}
	
	public static double[] INF(double[][] T, double[] v)
	{
		int n = T.length;
		for(int rep = 0;rep < 400;rep++){
			double[][] U = p2(T);
			double norm = 0;
			for(int i = 0;i < n;i++){
				for(int j = 0;j < n;j++){
					double d = T[i][j]-U[i][j];
					norm += d*d;
				}
			}
			if(norm < 1e-11)break;
//			if(norm == 0)break;
			T = U;
		}
		return mul(T, v);
	}
	
	public static double[] mul(double[][] A, double[] v)
	{
		int m = A.length;
		int n = v.length;
		double[] w = new double[m];
		for(int i = 0;i < m;i++){
			double sum = 0;
			for(int k = 0;k < n;k++){
				sum += A[i][k] * v[k];
			}
			w[i] = sum;
		}
		return w;
	}
	
	public static double[][] p2(double[][] A)
	{
		int n = A.length;
		double[][] C = new double[n][n];
		for(int i = 0;i < n;i++){
			for(int k = 0;k < n;k++){
				for(int j = 0;j < n;j++){
					C[i][j] += A[i][k] * A[k][j];
				}
			}
		}
		return C;
	}

	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new D().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Frog in Maze C++ Solution

Frog in Maze Java8 Solution

Frog in Maze Java7 Solution

Leave a Reply