Home >Backend Development >C++ >A matrix probability problem?
Here we will see a matrix probability problem. We have a rectangular matrix. We can move in four directions from the current cell with equal probability. The four directions are left, right, up, and down. We want to calculate the probability after N moves starting from position M[i,j].
Here we have to do some things related to DFS. We will recursively traverse the four possible rooms starting from the current room. Then we calculate the probability of taking one less step. Since the four directions have equal probabilities, each direction will contribute 0.25 of the total probability. We will return 0 if a matrix boundary is crossed and 1 when N moves are completed. Let's look at the algorithm to get this idea.
Begin if x,y is not in matrix boundary m, n, then return 0 if N is 0 , then return 1 prob := 0 prob := prob + matProb(m, n, x-1, y, N-1) * 0.25 prob := prob + matProb(m, n, x+1, y, N-1) * 0.25 prob := prob + matProb(m, n, x, y+1, N-1) * 0.25 prob := prob + matProb(m, n, x, y-1, N-1) * 0.25 return prob End
#include<iostream> using namespace std; bool isSafe(int x, int y, int m, int n) { //function to check whether (x,y) is in matrix or not if(x >= 0 && x < m && y >= 0 && y < n){ return true; } return false; } double matProb(int m, int n, int x, int y, int N) { if (!isSafe(x, y, m, n)) //if coundary is crossed return 0.0; if (N == 0) //when N is 0, or N is completed, return 1 return 1.0; double probability = 0.0; probability += matProb(m, n, x - 1, y, N - 1) * 0.25; //move left probability += matProb(m, n, x, y + 1, N - 1) * 0.25; //move up probability += matProb(m, n, x + 1, y, N - 1) * 0.25; //move right probability += matProb(m, n, x, y - 1, N - 1) * 0.25; //move down return probability; } int main() { int m = 7, n = 8; int x = 1, y = 1; int N = 4; cout << "Matrix Probability is " << matProb(m, n, x, y, N); }
Matrix Probability is 0.664062
The above is the detailed content of A matrix probability problem?. For more information, please follow other related articles on the PHP Chinese website!