LeetCode 200



两个思路：深度搜索或者并查集。
思路一：DFS  依次访问每一个点, 如果是'1'就进行DFS搜索, 访问过的地方可以改变他的值, 防止再次访问.
class Solution {
public:
    void DFS(vector<vector<char>>& grid, int i, int j)
    {
        if(i<0||j<0||i>=grid.size()||j>=grid[0].size()||grid[i][j]!='1') return;
        grid[i][j] = '2';
        DFS(grid, i+1, j);
        DFS(grid, i-1, j);
        DFS(grid, i, j+1);
        DFS(grid, i, j-1);
    }
    
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0) return 0;
        int cnt = 0, m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; i++)
            for(int j =0; j < n; j++)
                if(grid[i][j] == '1')
                {
                    cnt++;
                    DFS(grid, i, j);
                }
        return cnt;
    }
};

思路二：并查集
class Solution {  
public:  
    int find(int k, vector<int>& u){  
        return k == u[k] ? k : u[k] = find(u[k],u);  
    }  
    int numIslands(vector<vector<char>>& grid) {  
        int res = 0;  
        int m = grid.size();  
        if (!m) return 0;  
        int n = grid[0].size();  
        if (!n) return 0;  
        vector<int>us(grid.size()*grid[0].size());  
        //从右下角开始遍历  
        for (int i = m - 1; i >= 0; i--)  
            for (int j = n - 1; j >= 0; j--){  
                if (grid[i][j] != '0'){  
                    int k = i*n + j;  
                    //并查集  
                    int s = i != m - 1 && grid[i+1][j] != '0' ? find(k + n, us) : 0;  
                    int t = j != n - 1 && grid[i][j+1] != '0' ? find(k + 1, us) : 0;  
                    if (s == t){  
                        if (s) us[k] = s;  
                        else { us[k] = k; res++; }  
                    }  
                    else{  
                        if (!s) us[k] = t;  
                        else if (!t) us[k] = s;  
                        else{ us[k] = us[s] = us[t] = max(us[s], us[t]); res--; }  
                    }  
                }  
            }  
        return res;  
    }     
};  


                
        
        
                
    

宽度优先搜索(BFS，Breadth-First Search)也是搜索的手段之一。它与深度优先搜索类似，从某 个状态出发探索所有可以到达的状态。
与深度优先搜索的不同之处在于搜索的顺序，宽度优先搜索总是先搜索距离初始状态近的状态。 也就是说，它是按照开始状态→只需1次转移就可以到达的所有状态→只需2次转移就可以到达的 所有状态→……这样的顺序进行搜索。对于同一个状态，宽度优先搜索只经过一次，因此复杂度 为O(状态数×转移的方式)。
深度优先搜索(隐式地)利用了栈进行计算，而宽度优先搜索则利用了队列。搜索时首先将初始 状态添加到队列里，此后从队列的前端不断取出状态，把从该状态可以转移到的状态中尚未访 问过的部分加入队列，如此往复，直至队列被取空或找到了问题的解。通过观察这个队列，我们 可以就知道所有的状态都是按照距初始状态由近及远的顺序被遍历的。
来看下面这个题目
迷宫的最短路径 
给定一个大小为 N×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格 的通道移动。请求出从起点到终点所需的小步数。请注意，本题假定从起点一定可以移动 到终点。 
限制条件  N, M ≤ 100
宽度优先搜索按照距开始状态由近及远的顺序进行搜索，因此可以很容易地用来求短路径、 少操作之类问题的答案。这个问题中，状态仅仅是目前所在位置的坐标，因此可以构造成pair 或者编码成int来表达状态。当状态更加复杂时，就需要封装成一个类来表示状态了。转移的方 式为四方向移动，状态数与迷宫的大小是相等的，所以复杂度是O(4×N×M)=O(N×M)。 
宽度优先搜索中，只要将已经访问过的状态用标记管理起来，就可以很好地做到由近及远的搜索。 这个问题中由于要求短距离，不妨用d[N][M]数组把短距离保存起来。初始时用充分大的常 数INF来初始化它，这样尚未到达的位置就是INF，也就同时起到了标记的作用。 虽然到达终点时就会停止搜索，可如果继续下去直到队列为空的话，就可以计算出到各个位置的 短距离。此外，如果搜索到后，d依然为INF的话，便可得知这个位置就是无法从起点到达的 位置。 
在今后的程序中，使用像INF这样充分大的常数的情况还很多。不把INF当作例外，而是直接参 与普通运算的情况也很常见。这种情况下，如果INF过大就可能带来溢出的危险。 假设INF=231-1。例如想用d[nx][ny]=min(d[nx][ny], d[x][y]+1)来更新d[nx][ny]，就会 发生INF+1=-231的情况。这一问题中d[x][y]总不等于INF，所以没有问题。但是为了防止这样 的问题，一般会将INF设为放大2~4倍也不会溢出的大小。 因为要向4个不同方向移动，用dx[4]和dy[4]两个数组来表示四个方向向量。这样通过一个循 环就可以实现四方向移动的遍历。
const int INF = 100000000; 
// 使用pair表示状态时，使用typedef会更加方便一些 typedef pair P; 
// 输入 char maze[MAX_N][MAX_M + 1]; 
// 表示迷宫的字符串的数组
 int N, M;
 int sx,sy; 
// 起点坐标 
int gx, gy; 
 // 终点坐标 
int d[MAX_N][MAX_M]; 
 // 到各个位置的短距离的数组 
// 4个方向移动的向量
 int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; 
// 求从(sx, sy)到(gx, gy)的短距离 // 如果无法到达，则是INF 
int bfs() {
 queue
 que; 
 // 把所有的位置都初始化为INF 
for (int i = 0; i < N; i++) 
 for (int j = 0; j < M; j++) 
d[i][j] = INF; // 将起点加入队列，并把这一地点的距离设置为0 
 que.push(P(sx, sy)); 
d[sx][sy] = 0; 
 // 不断循环直到队列的长度为0 
while (que.size()) { 
// 从队列的前端取出元素 P 
p = que.front(); que.pop(); 
// 如果取出的状态已经是终点，则结束搜索 
 if (p.first == gx && p.second == gy) break; 
 // 四个方向的循环 
 for (int i = 0; i < 4; i++) { 
 // 移动之后的位置记为(nx, ny) 
 int nx = p.first + dx[i], ny = p.second + dy[i]; 
 // 判断是否可以移动以及是否已经访问过(d[nx][ny]!=INF即为已经访问过) 
 if (0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' &&d[nx][ny] == INF) { 
 // 可以移动的话，则加入到队列，并且到该位置的距离确定为到p的距离+1 
 que.push(P(nx, ny)); 
 d[nx][ny] = d[p.first][p.second] + 1; 
 } 
 } 
 } 
return d[gx][gy];
 } 
void solve() { int res = bfs(); printf("%d

Maze试验台的设计与实现（宽度优先搜索和深度优先搜索的理解）
一、 宽度优先搜索
BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。在一棵树上的搜索特点就是由根节点向深层逐层搜索，搜索完一层后再搜索下一层；在图中搜索方式类似于“波浪“，由根节点一层一层的向外搜索。

用队列实现宽度优先算法：

1、把根节点放到队列中。

2、每次从队列的头部取出一个元素v。判断节点v是否被访问：一、当节点v没有被访问时，执行步骤3、4、。二、v节点被访问时，则不需要对节点v进行任何操作，重复步骤2。

3、对于没有被访问的节点v要进行以下几个操作：一、判断当前节点v是否是目标goal，若是则返回目标，搜索结束。二、节点v不是目标节点，则将节点v标记为已访问，并将v的所有孩子节点集合w放在队列的末尾（对于一个图来说，则是与之相邻的上下四个节点）。注：对于v的孩子节点入队列前，加一个判断，将那些已访问或者是障碍物的孩子节点剔除）。

4、如果遍历整个树还没有找到，结束程序
def BFS(maze,v,goal,came_from):
    frontier=Queue()#声明一个队列
    frontier.enqueue(v)#将根节点v入队列尾
    came_from[v]=None#根节点的父节点为空
    while not frontier.is_empty():
        v=frontier.dequeue()#从队列头弹出一个节点
        if maze[v[0],v[1]]==Maze.EMPTY:#在v节点是已被访问或者是障碍物的时候，都无意义可直接跳过
            if v==goal:
                return v
            else:
                maze[v[0],v[1]]==Maze.OCCUPIED#当该节点不是目标节点时，将其标记为已访问，并将其子节点入队列尾
                for w in Maze.getAllMoves(v[0],v[1]):#Maze.getAllMoves()方法是获得与v节点相邻的所有节点
                    if w==Maze.EMPTY:#有选择的入队列，排除无意义的节点（必要性：***一定要剔除已被访问的节点，否则v扩展w入队列，然后w出队列，同时又同样的扩展v，从而进入死循环v,w不停地出入队列。***
                        frontier.enqueue(w)
                        came_from[w]=v
    return None


二、深度优先搜索
顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。也就是递归下去。否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路，这便是回溯上来。
递归实现
def DFS(maze,v,goal,came_from):
    if came_from=={}:
        came_from[v]=None
    if v==goal:
        return v
    maze[v[0],v[1]]==Maze.OCCUPIED
    for w in maze.getAllMOves(v[0],v[1]):
        if maze[w[0],w[1]]==Maze.EMPTY:
            came_from[w]=v
            result=DFS(maze,w,goal,came_from)
            if result==goal:
                return result
    return None

用栈实现
与宽度优先搜索很类似，但又有些差异。宽度是越深层的节点越后访问，所以先来的节点先访问，用队列储存；而深度优先搜索则相反，先来的节点后访问，所以用栈来储存。
def DFS(maze,v,goal,came_from):
    stack=Stack()
    stack.push(v)
    came_from[v]=None#根节点的父节点为空
    while not stack.is_empty():
        v=stack.pop()
        if maze[v[0],v[1]]==Maze.EMPTY:#在v节点是已被访问或者是障碍物的时候，都无意义可直接跳过
            if v==goal:
                return v
            else:
                maze[v[0],v[1]]=Maze.OCCUPIED#当该节点不是目标节点时，将其标记为已访问，并将其子节点入栈尾
                for w in maze.getAllMoves(v[0],v[1]):
                    if maze[w[0],w[1]]==Maze.EMPTY:#v的子节点有可能已被访问或者是障碍物，需判断。删除后程序卡死，为什么？
                        stack.push(w)            #关键在于有已被访问的节点入栈由v扩展出w，v出栈；然后访问w的时候，再由w扩展出v，因为v和w是相邻关系， v再入栈，这样就会形成死循环
                        came_from[w]=v
    return None

总结：深度优先搜索与宽度优先搜索之间的不同在分别用栈与队列实现的时候非常明显，归结为一点就是给节点赋予的优先级不同。