200. Number of Islands 133. Clone Graph 127. Word Ladder

求一个途中孤岛有多少个，可以采用深度优先的方法，当遇到1的时候就把四周变成0；

BFS方法

大致思路一致也是遇到1 的时候将四周变成0， 不过采用栈来处理，需要用一个数组来控制四个方向，上下左右。当然用二维的vector也是可以。如下代码。

// directional vectors to check adjacent cells (4-directional)
vector> dirs = {{0,-1},{0,1},{-1,0},{1,0}};
// handle adjacent cells for a given cell
for (int k = 0; k < 4; k++) {
    int r = p.first + dirs[k][0];
    int c = p.second + dirs[k][1];
    if (isValidCell(r,c,m,n) && grid[r][c] == '1') {
        grid[r][c] = '0';
        q.push({r,c});
    }
}

DFS直接用递归处理

class Solution {
public:
    int offsets[5] = {0,1,0,-1,0};
    int numIslands(vector>& grid) {
        int res=0, m=grid.size(), n=grid[0].size();
        
        for(int i=0; i>& grid, int i, int j){
        if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]=='0') return;
        grid[i][j]='0';
        DFS(grid, i+1, j);
        DFS(grid, i-1, j);
        DFS(grid, i, j+1);
        DFS(grid, i, j-1);
    }
    
    void BFS(vector>& grid, int i, int j){
        grid[i][j]='0';
        queue>q;
        q.push({i,j});
        while(!q.empty()){
            pair temp = q.front(); q.pop();
            for(int k=0; k<4; k++){
                //四个方向
                int r = temp.first + offsets[k] , c = temp.second + offsets[k+1];
                if(r>=0 && r< grid.size() && c>=0 && c 
133. Clone Graph 
就是把一个图再重新复制一遍，这个数据的格式是 val 和beighbors。需要采用一个map来确定这个节点是不是已经添加进去，如果没有将节点和他的neighbors加入进去。
 
DFS和BFS代码
 

class Solution {
public:
    map mp;
    Node* cloneGraph(Node* node) {
        //广度优先
        if(node==NULL) return NULL;
        //一个节点的引用
      
        if(mp.find(node) == mp.end()){
            mp[node] = new Node(node->val, {});
            for(Node* n: node->neighbors){
                mp[node] -> neighbors.push_back(cloneGraph(n));
            }
        }
        return mp[node];
    }
    Node* cloneGraph(Node* node){
        if( node == NULL) return NULL;
        Node* copy = new Node(node->val, {});
        mp[node] = copy;
        queue q;
        q.push(node);
        while(!q.empty()){
            Node* temp = q.front(); q.pop();
            for(auto n:temp->neighbors){
                if(mp.find(n) == mp.end()){
                    mp[n] = new Node(n->val, {});
                    q.push(n);
                }
                mp[temp] -> neighbors.push_back(mp[n]);
            }
            
        }
        return copy;
    }
    
    
    
};
 
127. Word Ladder 
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector& wordList) {
        unordered_set dict(wordList.begin(), wordList.end());
        if (dict.find(endWord) == dict.end()) return 0; //Not Found
        queue q;
        q.push(beginWord);
        int res =1;
        while(!q.empty()){
            int n=q.size();
            //只差一个字符的字符串
            for(int i=0; i