Java 中从左上角到右下角的矩阵可能路径

2024年9月10日 | 阅读 6 分钟

在本节中，我们将学习如何在Java中找到从矩阵左上角到右下角的可能路径。这是面试中一个非常重要的问题。从左上角到右下角的移动约束是，从任何单元格出发，只能向右（→）或向下（↓）移动。为了更好地理解，我们来看几个例子。

注意：建议读者先学习数组和递归，然后再阅读本主题。

示例

示例 1

4 2
8 0 
3 5

在上图的 3 * 3 矩阵中，需要从标记为 1 的单元格移动到标记为 5 的单元格。从单元格 1，可以移动到单元格 4 或单元格 7。同样，从单元格 4，可以移动到单元格 8 或单元格 2，从单元格 7，可以移动到单元格 6 或单元格 8。如此继续，将得到以下结果。

因此，我们看到有 6 种方法可以从标记为 1 的单元格到达标记为 5 的单元格。

示例 2

2 1 0 4
8 7 6 9

在上图的 2 * 4 矩阵中，将得到以下结果。

因此，我们看到有 4 种方法可以从标记为 2 的单元格到达标记为 9 的单元格。

使用递归

简单的递归足以解决这个问题。首先，我们显示所有向下移动的路径，然后显示所有向右移动的路径。我们将对路径中遇到的每个单元格进行递归处理。

实施

以下是打印矩阵从左上角到右下角可能路径的实现。

文件名： TopLeftBottomRightPath.java

// important import statement
import java.util.*;

public class TopLeftBottomRightPath
{
private void displayMatrix(int matrix[][], int r, int c, int x, int y, ArrayList<Integer> al)
{
// return if r or c goes out of  the range
if(x > r || y > c)
{
return;
}

al.add(matrix[x][y]);
// the bottom right cell has been reached
if(x == r && y == c)
{
System.out.println(al);
}

// recursively moving in the downward direction
displayMatrix(matrix, r, c, x + 1, y, al);

// recursively moving in the rightward direction
displayMatrix(matrix, r, c, x, y + 1, al);

al.remove(al.size() - 1);

}
	
// main method
public static void main(String[] argvs)
{
// number of rows
int r = 3;

// number of colums
int c = 3;

int m[][] = { { 1, 4, 2 },
	      { 7, 8, 0 },
	      { 6, 3, 5 }
                   };

// creating an object of the class ArrayList            
ArrayList<Integer> al = new ArrayList<Integer>();

// creating an object of the class TopLeftBottomRightPath
TopLeftBottomRightPath obj = new TopLeftBottomRightPath();

System.out.println("For the matrix: ");

for(int i = 0; i < r; i++)
{
    for(int j = 0; j < c; j++)
    {
        System.out.print(m[i][j] + " ");
    }
    
    System.out.println();
}

System.out.println();
System.out.println("The possible paths from the top left to the bottom right is: ");
obj.displayMatrix(m, r - 1, c - 1, 0, 0, al);
}
}

输出

For the matrix: 
1 4 2 
7 8 0 
6 3 5 

The possible paths from the top left to the bottom right is: 
[1, 7, 6, 3, 5]
[1, 7, 8, 3, 5]
[1, 7, 8, 0, 5]
[1, 4, 8, 3, 5]
[1, 4, 8, 0, 5]
[1, 4, 2, 0, 5]

使用迭代

我们也可以使用迭代来解决这个问题。在这种方法中，我们将使用广度优先搜索 (BFS)。将使用一个队列，其中包含单元格坐标和到特定单元格的路径。从左上角单元格开始，我们将单元格的坐标和值（单元格的值存储在向量中）推入队列。我们将继续探索向下和向右的单元格，直到队列不为空，并且还将继续将未发现的单元格推入队列。当我们到达矩阵的右下角单元格时，包含所探索单元格值的向量就是我们的答案。

// important import statements
import java.util.*;

// a class for storing the 
//cells of the matrix and its coordinates
class Store 
{
    
ArrayList<Integer> al;
int x;
int y;

Store()
{
this.al = new ArrayList<Integer>();   
}

// paramterized constructor of the class
Store(ArrayList<Integer> a, int x, int y)
{
// initializing the fields
this.al = new ArrayList<Integer>(a);
this.x = x;
this.y = y;
}

}

public class TopLeftExample
{
void displayllPaths(ArrayList<ArrayList<Integer>> m, int r, int c, Store obj)
{

Queue<Store> q = new LinkedList<Store>();

// get the value of the top left cell
int j = m.get(0).get(0);
obj.al.add(j);
obj.x = 0; obj.y = 0;

// adding the top-left cell into the queue
q.add(obj);

// run the loop until the queue is not empty
while (q.isEmpty() == false) 
{
obj = q.peek();
q.poll();

// the destination cell has been reached
// hence print the path
if (obj.x == r - 1 && obj.y == c - 1) 
{
for (int i = 0; i < obj.al.size(); i++)
{
System.out.print(obj.al.get(i) + " ");
}

System.out.println();
}

// we have reached the last row
// Hence, movement in the downward direction is not possible
// Only we can move in the right direction
else if (obj.x == r - 1) 
{
ArrayList<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < obj.al.size(); i++)
{
temp.add(obj.al.get(i));
}

// updating the current path
temp.add(m.get(obj.x).get(obj.y + 1));

q.add(new Store(temp, obj.x, obj.y + 1));
}

// we have reached the last column
// Hence, movement in the rightward direction is not possible
// Only we can move in the downward direction
else if (obj.y == c - 1) 
{
ArrayList<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < obj.al.size(); i++)
{
temp.add(obj.al.get(i));
}

// updating the current path
temp.add(m.get(obj.x + 1).get(obj.y));

q.add(new Store(temp, obj.x + 1, obj.y));
}

// movement in the right as well as movement in the 
// downward direction is possible
else 
{ 

ArrayList<Integer> temp = new ArrayList<Integer>();

for (int i = 0; i < obj.al.size(); i++)
{
temp.add(obj.al.get(i));
}

// updating the current path
temp.add(m.get(obj.x).get(obj.y + 1));

q.add(new Store(temp, obj.x, obj.y + 1));

// down movement
temp.remove(temp.size() - 1);

// updating the current path
temp.add(m.get(obj.x + 1).get(obj.y));

q.add(new Store(temp, obj.x + 1, obj.y));
}
}
}


// main method
public static void main (String argvs[])
{
// number of rows in the maze
int r = 3;

// number of columns in the maze
int c = 3;

// creating a 2-dimensional list
ArrayList<ArrayList<Integer>> maze = new ArrayList<ArrayList<Integer>>();
maze.add(new ArrayList<Integer>(Arrays.asList(1, 4, 2)));
maze.add(new ArrayList<Integer>(Arrays.asList(7, 8, 0)));
maze.add(new ArrayList<Integer>(Arrays.asList(6, 3, 5)));

System.out.println("For the following maze: ");
System.out.println(maze.get(0));
System.out.println(maze.get(1));
System.out.println(maze.get(2) + "\n");

// creating an object of the class TopLeftExample
TopLeftExample obj = new TopLeftExample();

// creating an object of the class Store
Store o = new Store();

System.out.println("The possible paths from the top left to the bottom right is: ");
obj.displayllPaths(maze, r, c, o);       
}
}

输出

For the following matrix: 
[1, 4, 2]
[7, 8, 0]
[6, 3, 5]

The possible paths from the top left to the bottom right is: 
1 4 2 0 5 
1 4 8 0 5 
1 4 8 3 5 
1 7 8 0 5 
1 7 8 3 5 
1 7 6 3 5

下一主题Java中的回文分割问题

Java 中从左上角到右下角的矩阵可能路径

注意：建议读者先学习数组和递归，然后再阅读本主题。

示例

示例 1

示例 2

使用递归

实施

使用迭代

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中从左上角到右下角的矩阵可能路径

注意：建议读者先学习数组和递归，然后再阅读本主题。

示例

示例 1

示例 2

使用递归

实施

使用迭代

相关帖子

Partition Number in Java

Java 中获取日期范围

How to Take Multiple String Input in Java Using Scanner

计算由不同元素子数组形成的对数（Java）

Java 将对象强制类型转换为类

DecimalStyle getDecimalSeparator() method in Java with Examples

Java 中的索引映射（或允许负数的平凡哈希）

用最少数量的矩形覆盖曼哈顿天际线

Java 中以毫秒为单位获取昨天的日期

Java 中的 Collectors.toCollection()

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器