JAVA算法：在二维数组中找到到达数组末尾（右下角）的最小步数（Steps）

JAVA算法：在二维数组中找到到达数组右下角位置的路径方法

给定一个由正整数组成的二维矩阵mat[]，任务是找到到达矩阵末尾（右下角）所需的最小步数。如果我们在单元格（i，j），我们可以转到单元格（i，j+arr[i][j]）或（i+arr[i][j]，j）。我们不能越界。如果没有路径，则打印-1。

例子：

给定数组：

 mat[][] = {
{2, 1, 2},
{1, 1, 1},
{1, 1, 1}

}
输出结果：2
路径为： {0, 0} -> {0, 2} -> {2, 2}
我们使用2步就可以达到该位置。

给定数组：

mat[][] = {
{1, 1, 1},
{1, 1, 1},
{1, 1, 1}

}
输出结果：4

我们需要4步（Steps）到达该位置

---

算法设计

package com.bean.algorithm.basic;

import java.util.LinkedList;
import java.util.Queue;

public class MinimumStepsReachEndofMatrix {
	
	static int n = 3;
	
	
	static class Pair {
		int first, second;

		Pair(int a, int b) {
			first = a;
			second = b;
		}
	}

	// Function to return the minimum steps
	// required to reach the end of the matrix
	static int minSteps(int arr[][]) {
		// Array to determine whether
		// a cell has been visited before
		boolean v[][] = new boolean[n][n];

		// Queue for bfs
		Queue<Pair> q = new LinkedList<Pair>();

		// Initializing queue
		q.add(new Pair(0, 0));

		// To store the depth of search
		int depth = 0;

		// BFS algorithm
		while (q.size() != 0) {

			// Current queue size
			int x = q.size();
			while (x-- > 0) {

				// Top-most element of queue
				Pair y = q.peek();

				// To store index of cell
				// for simplicity
				int i = y.first, j = y.second;
				q.remove();

				// Base case
				if (v[i][j])
					continue;

				// If we reach (n-1, n-1)
				if (i == n - 1 && j == n - 1)
					return depth;

				// Marking the cell visited
				v[i][j] = true;

				// Pushing the adjacent cells in the
				// queue that can be visited
				// from the current cell
				if (i + arr[i][j] < n)
					q.add(new Pair(i + arr[i][j], j));
				if (j + arr[i][j] < n)
					q.add(new Pair(i, j + arr[i][j]));
			}
			depth++;
		}
		return -1;
	}

	// Driver code
	public static void main(String args[]) {
//		int mat[][] = { 
//				{ 1, 1, 1 }, 
//				{ 1, 1, 1 }, 
//				{ 1, 1, 1 } 
//				};
		
		int mat[][] = {
				{2, 1, 2},
				{1, 1, 1},
				{1, 1, 1}
				};

		System.out.println(minSteps(mat));
	}
}

程序运行结果：

2