图 2019-04-20

图
实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
实现图的深度优先搜索、广度优先搜索
实现 Dijkstra 算法、A* 算法
实现拓扑排序的 Kahn 算法、DFS 算法
对应的 练习题
1Number of Islands（岛屿的个数）
英文版：https://leetcode.com/problems/number-of-islands/description/
中文版：https://leetcode-cn.com/problems/number-of-islands/description/

采用DFS深度优先搜索算法，从一个顶点开始，对一个路劲进行深入搜索直到尽头，之后查询其他路径；搜索完全部路径之后检查有没有其他顶点需要进行搜索。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        
        int m = grid.size();
        if(!m) return 0;
        int n = grid[0].size();
        int count = 2;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1')
                {
                    bl(grid, count, i, j, m, n);
                    count++;
                }
            }
        }
        return count - 2;
    }
    void bl(vector<vector<char>>& grid, int count, int i, int j, int m, int n)
    {
        grid[i][j] = (char)('0' + count);
        if (j + 1 < n && grid[i][j + 1] == '1') bl(grid, count, i, j + 1, m, n);
        if (i + 1 < m && grid[i + 1][j] == '1') bl(grid, count, i + 1, j, m, n);
        if (j - 1 >= 0 && grid[i][j - 1] == '1') bl(grid, count, i, j - 1, m, n);
        if (i - 1 >= 0 && grid[i - 1][j] == '1') bl(grid, count, i - 1, j, m, n);
    }


};

2Valid Sudoku（有效的数独）
英文版：https://leetcode.com/problems/valid-sudoku/
中文版：https://leetcode-cn.com/problems/valid-sudoku/

数独成九宫格排布，数字1~9在每行每列每个小九宫格均只会出现一次。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        const int cnt = 9;
        bool rowMap[cnt][cnt] = {false};        //行初始化
        bool colMap[cnt][cnt] = {false};        //列初始化
        bool smallBoardMask[cnt][cnt] = {false};//小九宫格初始化
        
        for(int i = 0; i < board.size(); ++i){  //行、列、小九都是9个，所以一个循环遍历
            for (int j = 0; j < board[i].size(); ++j){
                if (board[i][j] == '.'){
                    continue;
                }
                int idx =  board[i][j] - '0' - 1;
                
                // 行
                if (rowMap[i][idx] == true){
                    return false;
                }
                rowMap[i][idx] = true;
                
                // 列
                if (colMap[j][idx] == true) {
                    return false;
                }
                colMap[j][idx] = true;
                
                // 小九宫格
                int area = (i/3) * 3 + (j/3);
                if (smallBoardMask[area][idx] == true) {
                    return false;
                }
                smallBoardMask[area][idx] = true;
            }
        }
        
        return true;
    }
        
};