در این مطلب، روش محاسبه تعداد راه‌های رسیدن به مقصد در ماز بیان و پیاده‌سازی آن، در زبان‌های برنامه‌نویسی گوناگون انجام شده است. یک ماز با خانه‌های ۰ و ۱- داده شده است. هدف، پیدا کردن مسیر از (۰ ,۰) به (n-1, m-1) و هر مسیری که باید از طریق دستکم یک سلول که حاوی ۱- است از آن عبور شود. از یک خانه داده شده، انتظار می‌رود که فقط به سلول‌های (i+1, j) و (i, j+1) حرکت شود. برای درک بهتر مطلب، مثال زیر قابل توجه است.

Input: maze[][] = {
{۰, ۰, ۰, ۰},
{۰, -۱, ۰, ۰},
{-۱, ۰, ۰, ۰},
{۰, ۰, ۰, ۰}}
Output: 16

روش محاسبه تعداد راه‌های رسیدن به مقصد در ماز

اکنون، باید همه مسیرهایی که دستکم از یک سلول علامت زده شده می‌گذرند (سلول‌های حاوی ۱-) را پیدا کرد. اگر مسیری پیدا شود که از هیچ یک از خانه‌های علامت‌گذاری شده و همه سلول‌های ممکن از (۰ ,۰) تا (n-1, m-1) عبور نکند، می‌توان همه مسیرهایی را پیدا کرد که دستکم از یکی از سلول‌های علامت‌گذاری شده عبور کنند.

تعداد مسیرهایی که از آن‌ها عبور می‌شود = تعداد کل مسیرها – تعداد مسیرهایی که از هیچ یک از مسیرهای علامت‌گذاری شده عبور نمی‌کنند.

برای پیدا کردن تعداد کل مسیرهایی که از هیچ یک از سلول‌های علامت‌گذاری شده عبور نمی‌کنند و تعداد کل مسیرها از مبدا به مقصد، از محاسباتی به صورت m + n – ۲)! / (n – ۱)! * (m – ۱)!‎) استفاده می‌شود که در آن m و n تعداد سطرها و ستون‌ها هستند. در ادامه، پیاده‌سازی رویکرد بالا انجام شده است. 

پیاده‌سازی در ++C

// C++ implementation of the approach 
#include <bits/stdc++.h> 
using namespace std; 
#define R 4 
#define C 4 
  
// Function to return the count of possible paths 
// in a maze[R][C] from (0, 0) to (R-1, C-1) that 
// do not pass through any of the marked cells 
int countPaths(int maze[][C]) 
{ 
    // If the initial cell is blocked, there is no 
    // way of moving anywhere 
    if (maze[0][0] == -1) 
        return 0; 
  
    // Initializing the leftmost column 
    for (int i = 0; i < R; i++) { 
        if (maze[i][0] == 0) 
            maze[i][0] = 1; 
  
        // If we encounter a blocked cell in leftmost 
        // row, there is no way of visiting any cell 
        // directly below it. 
        else
            break; 
    } 
  
    // Similarly initialize the topmost row 
    for (int i = 1; i < C; i++) { 
        if (maze[0][i] == 0) 
            maze[0][i] = 1; 
  
        // If we encounter a blocked cell in bottommost 
        // row, there is no way of visiting any cell 
        // directly below it. 
        else
            break; 
    } 
  
    // The only difference is that if a cell is -1, 
    // simply ignore it else recursively compute 
    // count value maze[i][j] 
    for (int i = 1; i < R; i++) { 
        for (int j = 1; j < C; j++) { 
            // If blockage is found, ignore this cell 
            if (maze[i][j] == -1) 
                continue; 
  
            // If we can reach maze[i][j] from maze[i-1][j] 
            // then increment count. 
            if (maze[i - 1][j] > 0) 
                maze[i][j] = (maze[i][j] + maze[i - 1][j]); 
  
            // If we can reach maze[i][j] from maze[i][j-1] 
            // then increment count. 
            if (maze[i][j - 1] > 0) 
                maze[i][j] = (maze[i][j] + maze[i][j - 1]); 
        } 
    } 
  
    // If the final cell is blocked, output 0, otherwise 
    // the answer 
    return (maze[R - 1][C - 1] > 0) ? maze[R - 1][C - 1] : 0; 
} 
// Function to return the count of all possible 
// paths from (0, 0) to (n - 1, m - 1) 
int numberOfPaths(int m, int n) 
{ 
    // We have to calculate m+n-2 C n-1 here 
    // which will be (m+n-2)! / (n-1)! (m-1)! 
    int path = 1; 
    for (int i = n; i < (m + n - 1); i++) { 
        path *= i; 
        path /= (i - n + 1); 
    } 
    return path; 
} 
  
// Function to return the total count of paths 
// from (0, 0) to (n - 1, m - 1) that pass 
// through at least one of the marked cells 
int solve(int maze[][C]) 
{ 
  
    // Total count of paths - Total paths that do not 
    // pass through any of the marked cell 
    int ans = numberOfPaths(R, C) - countPaths(maze); 
  
    // return answer 
    return ans; 
} 
  
// Driver code 
int main() 
{ 
    int maze[R][C] = { { 0, 0, 0, 0 }, 
                       { ۰, -۱, ۰, ۰ }, 
                       { -۱, ۰, ۰, ۰ }, 
                       { ۰, ۰, ۰, ۰ } }; 
  
    cout << solve(maze); 
  
    return 0; 
}

پیاده‌سازی در جاوا

// Java implementation of the approach 
import java.io.*; 
  
class GFG  
{ 
static int R = 4; 
static int C = 4; 
  
// Function to return the count of possible paths 
// in a maze[R][C] from (0, 0) to (R-1, C-1) that 
// do not pass through any of the marked cells 
static int countPaths(int maze[][]) 
{ 
      
    // If the initial cell is blocked,  
    // there is no way of moving anywhere 
    if (maze[0][0] == -1) 
        return 0; 
  
    // Initializing the leftmost column 
    for (int i = 0; i < R; i++) 
    { 
        if (maze[i][0] == 0) 
            maze[i][0] = 1; 
  
        // If we encounter a blocked cell in leftmost 
        // row, there is no way of visiting any cell 
        // directly below it. 
        else
            break; 
    } 
  
    // Similarly initialize the topmost row 
    for (int i = 1; i < C; i++) 
    { 
        if (maze[0][i] == 0) 
            maze[0][i] = 1; 
  
        // If we encounter a blocked cell in bottommost 
        // row, there is no way of visiting any cell 
        // directly below it. 
        else
            break; 
    } 
  
    // The only difference is that if a cell is -1, 
    // simply ignore it else recursively compute 
    // count value maze[i][j] 
    for (int i = 1; i < R; i++)  
    { 
        for (int j = 1; j < C; j++)  
        { 
              
            // If blockage is found, ignore this cell 
            if (maze[i][j] == -1) 
                continue; 
  
            // If we can reach maze[i][j] from 
            //  maze[i-1][j] then increment count. 
            if (maze[i - 1][j] > 0) 
                maze[i][j] = (maze[i][j] +  
                              maze[i - 1][j]); 
  
            // If we can reach maze[i][j] from  
            // maze[i][j-1] then increment count. 
            if (maze[i][j - 1] > 0) 
                maze[i][j] = (maze[i][j] + 
                              maze[i][j - 1]); 
        } 
    } 
  
    // If the final cell is blocked,  
    // output 0, otherwise the answer 
    return (maze[R - 1][C - 1] > 0) ? 
                 maze[R - 1][C - 1] : 0; 
} 
  
// Function to return the count of all possible 
// paths from (0, 0) to (n - 1, m - 1) 
static int numberOfPaths(int m, int n) 
{ 
    // We have to calculate m+n-2 C n-1 here 
    // which will be (m+n-2)! / (n-1)! (m-1)! 
    int path = 1; 
    for (int i = n; i < (m + n - 1); i++) 
    { 
        path *= i; 
        path /= (i - n + 1); 
    } 
    return path; 
} 
  
// Function to return the total count of paths 
// from (0, 0) to (n - 1, m - 1) that pass 
// through at least one of the marked cells 
static int solve(int maze[][]) 
{ 
  
    // Total count of paths - Total paths that do not 
    // pass through any of the marked cell 
    int ans = numberOfPaths(R, C) - countPaths(maze); 
  
    // return answer 
    return ans; 
} 
  
// Driver code 
public static void main (String[] args)  
{ 
    int maze[][] = { { 0, 0, 0, 0 }, 
                     { ۰, -۱, ۰, ۰ }, 
                     { -۱, ۰, ۰, ۰ }, 
                     { ۰, ۰, ۰, ۰ } }; 
  
    System.out.println(solve(maze)); 
} 
} 
  
// This code is contributed by anuj_67..

پیاده‌سازی در پایتون ۳

# Python3 implementation of the approach 
R = 4
C = 4
  
# Function to return the count of  
# possible paths in a maze[R][C]  
# from (0, 0) to (R-1, C-1) that 
# do not pass through any of  
# the marked cells 
def countPaths(maze): 
      
    # If the initial cell is blocked,  
    # there is no way of moving anywhere 
    if (maze[0][0] == -1): 
        return 0
  
    # Initializing the leftmost column 
    for i in range(R): 
        if (maze[i][0] == 0): 
            maze[i][0] = 1
  
        # If we encounter a blocked cell  
        # in leftmost row, there is no way of  
        # visiting any cell directly below it. 
        else: 
            break
  
    # Similarly initialize the topmost row 
    for i in range(1, C): 
        if (maze[0][i] == 0): 
            maze[0][i] = 1
  
        # If we encounter a blocked cell in  
        # bottommost row, there is no way of  
        # visiting any cell directly below it. 
        else: 
            break
  
    # The only difference is that if  
    # a cell is -1, simply ignore it  
    # else recursively compute  
    # count value maze[i][j] 
    for i in range(1, R): 
        for j in range(1, C): 
              
            # If blockage is found,  
            # ignore this cell 
            if (maze[i][j] == -1): 
                continue
  
            # If we can reach maze[i][j] from  
            # maze[i-1][j] then increment count. 
            if (maze[i - 1][j] > 0): 
                maze[i][j] = (maze[i][j] + 
                              maze[i - 1][j]) 
  
            # If we can reach maze[i][j] from  
            # maze[i][j-1] then increment count. 
            if (maze[i][j - 1] > 0): 
                maze[i][j] = (maze[i][j] + 
                              maze[i][j - 1]) 
  
    # If the final cell is blocked,  
    # output 0, otherwise the answer 
    if (maze[R - 1][C - 1] > 0): 
        return maze[R - 1][C - 1] 
    else: 
        return 0
  
# Function to return the count of  
# all possible paths from  
# (۰, ۰) to (n - 1, m - 1) 
def numberOfPaths(m, n): 
  
    # We have to calculate m+n-2 C n-1 here 
    # which will be (m+n-2)! / (n-1)! (m-1)! 
    path = 1
    for i in range(n, m + n - 1): 
  
        path *= i 
        path //= (i - n + 1) 
  
    return path 
  
# Function to return the total count  
# of paths from (0, 0) to (n - 1, m - 1)  
# that pass through at least one  
# of the marked cells 
def solve(maze): 
      
    # Total count of paths - Total paths  
    # that do not pass through any of  
    # the marked cell 
    ans = (numberOfPaths(R, C) -
           countPaths(maze)) 
  
    # return answer 
    return ans 
  
# Driver code 
maze = [[ 0, 0, 0, 0 ], 
        [ ۰, -۱, ۰, ۰ ], 
        [ -۱, ۰, ۰, ۰ ], 
        [ ۰, ۰, ۰, ۰ ]] 
  
print(solve(maze)) 
  
# This code is contributed 
# by Mohit Kumar

پیاده‌سازی در #C

// C# implementation of the approach 
using System; 
class GFG  
{ 
static int R = 4; 
static int C = 4; 
  
// Function to return the count of possible paths 
// in a maze[R][C] from (0, 0) to (R-1, C-1) that 
// do not pass through any of the marked cells 
static int countPaths(int [,]maze) 
{ 
      
    // If the initial cell is blocked,  
    // there is no way of moving anywhere 
    if (maze[0, 0] == -1) 
        return 0; 
  
    // Initializing the leftmost column 
    for (int i = 0; i < R; i++) 
    { 
        if (maze[i, 0] == 0) 
            maze[i, 0] = 1; 
  
        // If we encounter a blocked cell in leftmost 
        // row, there is no way of visiting any cell 
        // directly below it. 
        else
            break; 
    } 
  
    // Similarly initialize the topmost row 
    for (int i = 1; i < C; i++) 
    { 
        if (maze[0, i] == 0) 
            maze[0, i] = 1; 
  
        // If we encounter a blocked cell in  
        // bottommost row, there is no way of  
        // visiting any cell directly below it. 
        else
            break; 
    } 
  
    // The only difference is that if a cell is -1, 
    // simply ignore it else recursively compute 
    // count value maze[i][j] 
    for (int i = 1; i < R; i++)  
    { 
        for (int j = 1; j < C; j++)  
        { 
              
            // If blockage is found, ignore this cell 
            if (maze[i, j] == -1) 
                continue; 
  
            // If we can reach maze[i][j] from 
            // maze[i-1][j] then increment count. 
            if (maze[i - 1, j] > 0) 
                maze[i, j] = (maze[i, j] +  
                              maze[i - 1, j]); 
  
            // If we can reach maze[i][j] from  
            // maze[i][j-1] then increment count. 
            if (maze[i, j - 1] > 0) 
                maze[i, j] = (maze[i, j] + 
                              maze[i, j - 1]); 
        } 
    } 
  
    // If the final cell is blocked,  
    // output 0, otherwise the answer 
    return (maze[R - 1, C - 1] > 0) ? 
            maze[R - 1, C - 1] : 0; 
} 
  
// Function to return the count of all possible 
// paths from (0, 0) to (n - 1, m - 1) 
static int numberOfPaths(int m, int n) 
{ 
    // We have to calculate m+n-2 C n-1 here 
    // which will be (m+n-2)! / (n-1)! (m-1)! 
    int path = 1; 
    for (int i = n; i < (m + n - 1); i++) 
    { 
        path *= i; 
        path /= (i - n + 1); 
    } 
    return path; 
} 
  
// Function to return the total count of paths 
// from (0, 0) to (n - 1, m - 1) that pass 
// through at least one of the marked cells 
static int solve(int [,]maze) 
{ 
  
    // Total count of paths - Total paths that do not 
    // pass through any of the marked cell 
    int ans = numberOfPaths(R, C) -  
              countPaths(maze); 
  
    // return answer 
    return ans; 
} 
  
// Driver code 
public static void Main ()  
{ 
    int [,]maze = {{ 0, 0, 0, 0 }, 
                   { ۰, -۱, ۰, ۰ }, 
                   { -۱, ۰, ۰, ۰ }, 
                   { ۰, ۰, ۰, ۰ }}; 
  
    Console.Write(solve(maze)); 
} 
} 
  
// This code is contributed by anuj_67..

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

منبع [+]