5. LintCode 宽度优先搜索（一）

LintCode 433：岛屿的个数

https://www.lintcode.com/problem/number-of-islands

描述

给一个01矩阵，求不同的岛屿的个数
0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

样例

输入：
[
  [1,1,0,0,0],
  [0,1,0,0,1],
  [0,0,0,1,1],
  [0,0,0,0,0],
  [0,0,0,0,1]
]
输出：
3
输入：
[
  [1,1]
]
输出：
1

解题思路

遍历矩阵，碰到1的节点对其进行宽搜寻找相邻为1的节点。遍历过的1节点将其置为0表示已经被查找过。

AC代码

public class Solution {
    public int numIslands(boolean[][] grid) {
        // 边界条件
        if (grid == null) { return 0; }
        int n = grid.length;
        if (n < 1) { return 0; }
        int m = grid[0].length;
        int ans = 0;
        // 遍历矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    // 碰到1的节点岛屿数加 1
                    ans++;
                    // 对节点为1的节点进行宽搜
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }
    private void dfs(boolean[][] grid, int x, int y) {
        // 4个相邻节点的走法
        int[] a = {0, 0, 1, -1};
        int[] b = {1, -1, 0, 0};
        int n = grid.length;
        int m = grid[0].length;
        // 宽搜队列
        Deque<Location> deque = new ArrayDeque<>();
        Location now = new Location(x, y);
        grid[x][y] = false;
        deque.add(now);
        while (!deque.isEmpty()) {
            // 当前有多少个节点可以扩展
            int size = deque.size();
            // 扩展这size个节点
            for (int i = 0; i < size; i++) {
                Location next = deque.removeFirst();
                for (int j = 0; j < 4; j++) {
                    int xx = next.x + a[j];
                    int yy = next.y + b[j];
                    if (xx >= 0 && xx < n && yy >= 0 && yy < m && grid[xx][yy]) {
                        Location add = new Location(xx, yy);
                        grid[xx][yy] = false;
                        deque.add(add);
                    }
                }
            }
        }
    }
}
// 定义一个坐标类
class Location{
    int x;
    int y;
    Location(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

LintCode 611：骑士的最短路线

https://www.lintcode.com/problem/knight-shortest-path

描述

给定骑士在棋盘上的 初始 位置(一个2进制矩阵 0 表示空 1 表示有障碍物)，找到到达 终点 的最短路线，返回路线的长度。如果骑士不能到达则返回 -1
起点跟终点必定为空.
骑士不能碰到障碍物.
路径长度指骑士走的步数

说明

如果骑士的位置为 (x,y)，他下一步可以到达以下这些位置:

(x + 1, y + 2)
(x + 1, y - 2)
(x - 1, y + 2)
(x - 1, y - 2)
(x + 2, y + 1)
(x + 2, y - 1)
(x - 2, y + 1)
(x - 2, y - 1)

样例

输入:
[[0,0,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] 
输出: 2
解释:
[2,0]->[0,1]->[2,2]
输入:
[[0,1,0],
 [0,0,1],
 [0,0,0]]
source = [2, 0] destination = [2, 2] 
输出:-1

解题思路

简单宽搜，从起点开始按骑士的走法，将骑士下一步能到达的位置加入宽搜队列，一步一步拓展知道队列为空或走到终点

AC代码

public int shortestPath(boolean[][] grid, Point source, Point destination) {
    // 
    if (source.x == destination.x && destination.y == source.y) {
        return 0;
    }
    int n = grid.length, m = grid[0].length;
    int ans = 0;
    int[] a = {1, 1, -1, -1, 2, 2, -2, -2};
    int[] b = {2, -2, 2, -2, 1, -1, 1, -1};
    Deque<Point> deque = new ArrayDeque<>();
    deque.add(source);
    while (!deque.isEmpty()) {
        Deque<Point> nDeque = new ArrayDeque<>();
        ans++;
        for (Point now : deque) {
            for (int i = 0; i < 8; i++) {
                int x = now.x + a[i];
                int y = now.y + b[i];
                if (x >= 0 && x < n && y >= 0 && y < m && !grid[x][y]) {
                    if (x == destination.x && y == destination.y) {
                        return ans;
                    }
                    Point next = new Point(x, y);
                    nDeque.add(next);
                    grid[x][y] = true;
                }
            }
        }
        deque = nDeque;
    }
    return -1;
}

LintCode 137：克隆图

https://www.lintcode.com/problem/clone-graph

描述

克隆一张无向图. 无向图的每个节点包含一个 label 和一个列表 neighbors. 保证每个节点的 label 互不相同.
你的程序需要返回一个经过深度拷贝的新图. 新图和原图具有同样的结构, 并且对新图的任何改动不会对原图造成任何影响.
你需要返回与给定节点具有相同 label 的那个节点.

样例

输入:
{1,2,4#2,1,4#4,1,2}
输出: 
{1,2,4#2,1,4#4,1,2}
解释:
1------2  
 \     |  
  \    |  
   \   |  
    \  |  
      4

解题思路

因为要克隆每个节点所包含的邻居节点，所以用一个map存储label对应的节点。
从 node 节点开始宽搜，碰到一个新节点（没在map中出现过），就复制一个存入map中。
每次从宽搜队列中取出一个节点，然后将其邻居也复制到克隆图中。
直到克隆完成。

AC代码

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    // 空直接返回
    if (node == null) { return null; }
    // 宽搜队列
    Deque<UndirectedGraphNode> deque = new ArrayDeque<>();
    // map存储label对应的节点
    Map<Integer, UndirectedGraphNode> map = new HashMap<>();
    // 克隆node
    map.put(node.label, new UndirectedGraphNode(node.label));
    deque.add(node);
    while (!deque.isEmpty()) {
        // 取出队列的首节点
        UndirectedGraphNode newNode = deque.removeFirst();
        // 取出克隆节点
        UndirectedGraphNode copy = map.get(newNode.label);
        // 复制neighbors
        for (UndirectedGraphNode tmp : newNode.neighbors) {
            // 克隆新节点
            if (!map.containsKey(tmp.label)) {
                UndirectedGraphNode newTmp = new UndirectedGraphNode(tmp.label);
                map.put(tmp.label, newTmp);
                deque.add(tmp);
            }
            copy.neighbors.add(map.get(tmp.label));
        }
    }
    return map.get(node.label);
}

LintCode 127：拓扑排序

https://www.lintcode.com/problem/topological-sorting

描述

给定一个有向图，图节点的拓扑排序定义如下:

• 对于图中的每一条有向边 A -> B , 在拓扑排序中A一定在B之前.
• 拓扑排序中的第一个节点可以是图中的任何一个没有其他节点指向它的节点.

针对给定的有向图找到任意一种拓扑排序的顺序.
你可以假设图中至少存在一种拓扑排序

样例

例如下图：

拓扑排序可以为：

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]

解题思路

题目只给了一个有向图，没有给出起点，所以要先做预处理，找出起点。统计所有点的入度（有多少条有向边指向它），当一个点的入度不为0时，代表着它前面还有节点，它还不能加入拓扑排序中；当入度为0时，便可加入拓扑排序中，此时它指向的节点的入度都减1，如果减到了0，那么该节点是新的可以加入拓扑排序的节点。正好用宽搜可以解决。

AC代码

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    // 预处理，统计每个节点的入度
    // 存储label对应的节点map
    Map<Integer, DirectedGraphNode> map = new HashMap<>();
    // 存储节点对应的入度
    Map<Integer, Integer> cmap = new HashMap<>();
    for (DirectedGraphNode tmp : graph) {
        int label = tmp.label;
        map.put(label, tmp);
        if (!cmap.containsKey(label)) {
            cmap.put(label, 0);
        }
        for (DirectedGraphNode neighber : tmp.neighbors) {
            int lab = neighber.label;
            if (!cmap.containsKey(lab)) {
                cmap.put(lab, 1);
            }
            else {
                cmap.put(lab, cmap.get(lab) + 1);
            }
        }
    }
    // 存储拓扑顺序
    ArrayList<DirectedGraphNode> ans = new ArrayList<>();
    // 宽搜队列
    Deque<DirectedGraphNode> deque = new ArrayDeque<>();
    // 入度为0的节点作为宽搜的起点
    for (Integer count : cmap.keySet()) {
        if (cmap.get(count) == 0) {
            DirectedGraphNode node = map.get(count);
            deque.add(node);
            ans.add(node);
        }
    }
    while (!deque.isEmpty()) {
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            DirectedGraphNode now = deque.removeFirst();
            // 每个走出队列节点指向的节点入度都要减一，入度为0了加入宽搜队列
            for (DirectedGraphNode next : now.neighbors) {
                int count = cmap.get(next.label);
                count--;
                if (count == 0) {
                    deque.add(next);
                    ans.add(next);
                }
                cmap.put(next.label, count);
            }
        }
    }
    return ans;
}

LintCode 120：单词接龙

https://www.lintcode.com/problem/word-ladder

描述

给出两个单词（start和end）和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。
变换规则如下：

1. 每次只能改变一个字母。
2. 变换过程中的中间单词必须在字典中出现。(起始单词和结束单词不需要出现在字典中)

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

样例

输入：start = "a"，end = "c"，dict =["a","b","c"]
输出：2
解释：
"a"->"c"
输入：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"]
输出：5
解释：
"hit"->"hot"->"dot"->"dog"->"cog"

解题思路

BFS，从start单词开始搜索，每个单词一次都有25length种变换，都是一个中间状态，相当于一个单词是一个节点，它可以指向25length个节点，end是最后要到达的节点，这样就变成了了前面遇到过的最短路线问题，用bfs可以解决。

AC代码

public int ladderLength(String start, String end, Set<String> dict) {
    // 将end加入dict中。
    dict.add(end);
    // 存储已经搜索过的单词
    Set<String> set = new HashSet<>();
    // 宽搜队列
    Deque<String> deque = new ArrayDeque<>();
    deque.add(start);
    // length 代表做了几下转换
    int length = 1;
    // 宽搜过程
    while (!deque.isEmpty()) {
        length++;
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            String word = deque.removeFirst();
            for (String nextWord : getNextWords(word, dict)) {
                if (set.contains(nextWord)) {
                    continue;
                }
                if (nextWord.equals(end)) {
                    return length;
                }
                set.add(nextWord);
                deque.add(nextWord);
            }
        }
    }
    return 0;
}
// 获取单词能转换到的在dict中的单词
private List<String> getNextWords(String word, Set<String> dict) {
    List<String> list = new ArrayList<>();
    for (char c = 'a'; c <= 'z'; c++) {
        for (int i = 0; i < word.length(); i++) {
            if (c == word.charAt(i)) {
                continue;
            }
            String nextWord = replaceWord(word, i, c);
            if (dict.contains(nextWord)) {
                list.add(nextWord);
            }
        }
    }
    return list;
}
private String replaceWord(String word, int i, char c) {
    char[] chars = word.toCharArray();
    chars[i] = c;
    return new String(chars);
}