题解 | #岛屿数量#

/**
 * 判断岛屿数量
 * @param grid char字符型二维数组 
 * @param gridRowLen int grid数组行数
 * @param gridColLen int* grid数组列数
 * <a href="/profile/756076230" data-card-uid="756076230" class="js-nc-card" target="_blank" from-niu="default">@return int整型
 */

void dfs(char** grid, int i,int j,int gridRowLen,int* gridColLen)
{
    int k,l;
    grid[i][j]='0';   //把所有的1都变成0
    for(k=-1;k<2;k++)  //-1,0,1 行 向左，不动，向右三种情况,这样写可以省去很多代码
    {
        for(l=-1;l<2;l++)
        {
            if(k==0&&l==0)  // //横纵坐标不变
            continue;
            if(i+k>=0&& i+k<=gridRowLen-1 &&j+l>=0 && j+l<=gridColLen[i]-1)
            {
                if(grid[i+k][j+l]=='1')
                dfs(grid, i+k,j+l,gridRowLen,gridColLen);
            }
        }
    }
}

int solve(char** grid, int gridRowLen, int* gridColLen ) {
    // write code here
    //其实这题类似与水洼题
    //1代表是陆地，0代表海洋,尝试把所有的1都变成0就可以完成
    int count=0;  //计数
    int i,j;
    for(i=0;i<gridRowLen;i++)
    {
        for(j=0;j<gridColLen[i];j++)
        {
            if(grid[i][j]=='1')
            {
                dfs(grid,i,j,gridRowLen,gridColLen);
                count++;
            }
        }
    }
  return count;
}
</a>

有一个大小为NxM的园子，兩后积起了水。八连通的积水被认为是连接在一起的。请求出
园子里总共有多少水洼? (八连通指的是 下图中相对W的*的部分)
(就是W是积水，以w为中心的八个方向找，分别八个方向都没w为止）
 ***
 *w*
 ***
I
限制条件
N, M<=100
样例:
输入
N=10, M=12
园子如下图('W'表示积水，'. '表示没有积水)

W........WW.
.WWW.....WWW
....WW...WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
 输出3

水洼的思路就是找到W把W消成. 并且不用回溯，因为已经全部变成点了


//#define M 12
//#define N 10
int N,M;
void dfs(char a[][12],int i,int j)
{
    a[i][j] = '.';  //把w变成点
    for (int k = -1; k < 2; k++)
    {//-1,0,1 行 向左，不动，向右三种情况
        for (int L = -1; L < 2; L++)
        {//-1向上,0不动,1向下
            if (k == 0 && L== 0) continue;  //横纵坐标不变没变的
            if (i + k >= 0 && i + k <= N - 1 && j + L >= 0 && j + L <= M - 1)
            {//i+k是行数，j+L是列数
                if (a[i + k][j + L] == 'W')
                    dfs(a, i + k, j + L);  //新的坐标
            }
        }
    }
}

int main()
{

    scanf("%d%d",&N,&M);
    char a[10][12];
    for(int i=0;i<N-1;i++)
    {
        scanf("%s",a[i]); //一行一行相当于字符串一行一行的输入
    }
    //找有w的点
    int count=0;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            if(a[i][j]=='W')
            {
                dfs(a,i,j);  //找一个起点开始清除一个水洼
                count++;
            }
        }
    }
    printf("\n水洼数=%d\n",count);
}