leetcode.200岛屿数量

时间:2020-01-05 vdk 人气:6

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

因为以前做过，所以照抄了，在x和y和对应的grid.size()和gird[0].size()上混淆了，所以出现溢出的报错后花了很长时间检查错误。

class Solution {
public:
struct queue{
    int x[30000];
    int y[30000];
    int head,tail;
}qqq;
int visited[1000][1000];
int enqueue(int o,int p,vector<vector<char>>& grid){
    if((qqq.tail+1)%500==qqq.head){
        return 0;
    }
    if(o<0||o>=grid.size()||p<0||p>=grid[0].size()){
        return 0;
    }
    if(visited[o][p]!=0||grid[o][p]=='0'){
        return 0;
    }
    cout<<o<<" "<<p<<"enqueue\n";
    qqq.x[qqq.tail]=o;
    qqq.y[qqq.tail]=p;
    visited[o][p]=1;
    qqq.tail++;
    return 1;
}
int dequeue(){
    if(qqq.head==qqq.tail){
        return 0;
    }
    qqq.head++;
    return 1;
}
bool isempty(){
    if(qqq.head==qqq.tail){
        return true;
    }
    return false;
}
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0||grid[0].size()==0) return 0;
        int count=0;
    qqq.head=0;
    qqq.tail=0;
    int f,g;
    int i,j;
    for(i=0;i<grid.size();i++){
        for(j=0;j<grid[i].size();j++){
            visited[i][j]=0;
        }
    }
    for(i=0;i<grid.size();i++){
        for(j=0;j<grid[i].size();j++){
            if(grid[i][j]=='1'&&visited[i][j]==0){
            enqueue(i,j,grid);
            while (!isempty()){
                f=qqq.x[qqq.head];
                g=qqq.y[qqq.head];
                visited[f][g]=count+1;
                dequeue();
                enqueue(f-1,g,grid);
                enqueue(f+1,g,grid);
                enqueue(f,g+1,grid);
                enqueue(f,g-1,grid);
            }
            count++;
        }
    }
}
return count;
    }
};

加载全部内容