図2019-04-20

図は有向図、無向図、有権図、無権図の隣接行列と隣接表表現方法実現図の深さ優先探索、広さ優先探索実現Dijkstraアルゴリズム、A*アルゴリズム実現トポロジーソートのKahnアルゴリズム、DFSアルゴリズム対応の練習問題1 Number of Islands(島の個数)英語版を実現する.https://leetcode.com/problems/number-of-islands/description/日本語版:https://leetcode-cn.com/problems/number-of-islands/description/
DFS深度優先探索アルゴリズムを採用し、1つの頂点から始まり、1つの道路力を突き当たりまで深く探索し、その後、他の経路を照会する.完全なパスを検索した後、他の頂点が検索する必要があるかどうかを確認します.

class Solution {
public:
    int numIslands(vector>& 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>& 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);
    }


};

2 Valid Sudoku(有効な数独)英語版:https://leetcode.com/problems/valid-sudoku/日本語版:https://leetcode-cn.com/problems/valid-sudoku/
数独が九宮格に並び、数字1~9は行ごとに小九宮格ごとに1回しか現れない.

class Solution {
public:
    bool isValidSudoku(vector>& 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;
    }
        
};