LeetCode 934. 最短的桥（2次BFS）

示例 1：
输入：[[0,1],[1,0]]
输出：1

示例 2：
输入：[[0,1,0],[0,0,0],[0,0,1]]
输出：2

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

提示：
1 <= A.length = A[0].length <= 100
A[i][j] == 0 或 A[i][j] == 1

class Solution {
	vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};//移动方向
public:
    int shortestBridge(vector<vector<int>>& A) {
        queue<pair<int,int>> q;//第二次BFS用的队列
        queue<pair<int,int>> firstLand;//第一次BFS用的队列
        int i, j, n = A.size(), k, x, y, step=0, size;
        bool found = false;
        vector<vector<bool>> visited(n,vector<bool> (n, false));
        for(i = 0; i < n; ++i)
        {
        	for(j = 0; j < n; ++j)
        		if(A[i][j])
        		{
        			q.push(make_pair(i,j));
        			firstLand.push(make_pair(i,j));
        			visited[i][j] = true;
        			found = true;
        			break;
        		}
    		if(found)
    			break;
        }
        pair<int,int> tp;
        while(!firstLand.empty())//第一次BFS
        {
        	tp = firstLand.front();
        	firstLand.pop();
        	for(k = 0; k < 4; ++k)
        	{
        		x = tp.first + dir[k][0];
        		y = tp.second + dir[k][1];
        		if(x>=0 && x<n && y>=0 && y<n && A[x][y] && !visited[x][y])
        		{
        			firstLand.push(make_pair(x,y));
        			q.push(make_pair(x,y));//q里存储了所有的第一个岛的点
        			visited[x][y] = true;
        		}
        	}
        }
        found = false;
        while(!q.empty())//第二次BFS
        {
        	size = q.size();
        	while(size--)//向外扩展一层
        	{
	        	tp = q.front();
	        	q.pop();
	        	for(k = 0; k < 4; ++k)
	        	{
	        		x = tp.first + dir[k][0];
	        		y = tp.second + dir[k][1];
	        		if(x>=0 && x<n && y>=0 && y<n && !visited[x][y])
	        		{
	        			if(A[x][y] == 0)
	        			{
	        				q.push(make_pair(x,y));
	        				visited[x][y] = true;
	        			}
	        			else//找到1了，连通了
	        			{
	        				found = true;
	        				break;
	        			}
	        		}
	        	}
	        	if(found)
	        		break;
	    	}
            step++;
	    	if(found)
	    		break;
            
        }
        return step-1;//最后一步1不算，所以-1
    }
};