题目描述

给定表示地图上坐标的2D数组，地图上只有值0,1,2.0表示可以通过，1表示不可通过，2表示目标位置。从坐标[0,0]开始，你只能上，下，左，右移动。找到可以到达目的地的最短路径，并返回路径的长度。

（地图一定存在且不为空，并且只存在一个目的地）

样例1
输入:
[
[0, 0, 0],
[0, 0, 1],
[0, 0, 2]
]
输出: 4
说明: [0,0] -> [1,0] -> [2,0] -> [2,1] -> [2,2]

样例2
输入:
[
[0,1],
[0,1],
[0,0],
[0,2]
]

输出: 4

说明: [0,0] -> [1,0] -> [2,0] -> [3,0] -> [3,1]

题目解析

1.此题类似骑士遍历题，但骑士遍历题的检查target是检查坐标，这题是检查value。所以如果在struct Point里面加上value这一项要确保target=2的值没有被改掉。

2.此题不需要visited map，因为可以简单的将targetMap[i][j]设为1，这样下次就不用再访问了。

3.In the validPlace(), 要确保先检查p.x和p.y的范围，然后再检查grid[p.x][p.y]的值，不然就segment fault。

参考代码

* 本参考程序来自九章算法，由 @九章算法助教团队 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param targetMap: 
     * @return: nothing
     */
    public int shortestPath(int[][] targetMap){
        // Write your code here
        int lenPath = 0;
        int targetX = 0;
        int targetY = 0;
        for (int i = 0; i < targetMap.length; i++) {
            for (int j = 0; j < targetMap[0].length; j++) {
                if (targetMap[i][j] == 2) {
                    targetX = i;
                    targetY = j;
                }
            }
        }
        lenPath = bfs(targetMap, targetX, targetY);
        return lenPath;
    }   
    int[] dx = { 0, 1, 0, -1 };
    int[] dy = { 1, 0, -1, 0 };
    public int bfs(int[][] targetMap, int targetX, int targetY) {
        int height = targetMap.length;
        int width = targetMap[0].length;
        Queue<Point> q = new LinkedList<Point>();
        q.offer(new Point(0, 0));
        int[][] deep = new int[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                deep[i][j] = -1;
            }
        }
        deep[0][0] = 0;
        while (q.size() > 0) {
            Point p = q.poll();
            if (p.x == targetX && p.y == targetY) {
                break;
            }
            for (int i = 0; i < 4; i++) {
                int x = p.x + dx[i];
                int y = p.y + dy[i];
                if (x >= 0 && x < height && y >= 0 && y < width && targetMap[x][y] != 1 && deep[x][y] == -1) {
                    deep[x][y] = deep[p.x][p.y] + 1;
                    q.offer(new Point(x, y));
                }
            }
        }
        return deep[targetX][targetY];
    }
}

点击 LintCode 进行在线评测