【编程题】挺有意思的一道题,老铁们还有更好的思路吗?

卫星拍摄的地面遥感图像是一个NxN的网络,每个网格或者是树木(用T表示)或者是空地(用B表示),如果树木网格的邻居(或上或下或左或右)网格也是树木,则它们属于同一片森林。试设计算法,统计遥感图像区域的森林数量。

例:下图中的森林数量为3。

int count(char **map, int N) //map是遥感图像,N是图像大小。

以下是我的思路:
#include <stdio.h>

int count(char **map, int n) //map是遥感图像,n是图像大小
{
    int count = 0;
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<n;j++)
        {
            char *c = (char *)map + i * n + j; //当前字符地址
            char *c_up = i >0 ? (char *)map + (i-1) * n + j : c; //上
            char *c_right = j < (n-1) ? (char *)map + i * n + j + 1 : c;//右
            char *c_down = i < (n-1) ? (char *)map + (i+1) * n + j : c;//下
            char *c_left = j>0 ? (char *)map + i * n + j : c;//左

            if(*c == 'T' || *c == 'Y')
            {
                if(*c == 'T' && *c_up!='Y' && *c_right!='Y' && *c_down!='Y' && *c_left!='Y')
                {
                    count++;
                    *c = 'Y';
                }

                //成片标记
                if(*c_up == 'T') *c_up = 'Y';
                if(*c_right == 'T') *c_right = 'Y';
                if(*c_down == 'T') *c_down = 'Y';
                if(*c_left == 'T') *c_left = 'Y';
            }
        }
    }

    return count;
}

int main() {

    //3个森林
    char map1[4][4] = {{'T','T','B','B'}, {'T','B','T','B'}, {'T','T','B','T'}, {'B','B','T','T'}};
    printf("%d\n", count((char **)map1, 4));

    //8个森林
    char map2[6][6] = {{'T','T','B','T','B','T'}, {'B','B','T','T','T','B'}, {'B','T','B','B','B','T'}, {'T','B','B','B','B','B'},{'T','T','B','T','B','T'},{'T','T','B','T','B','T'}};
    printf("%d\n", count((char **)map2, 6));

    return 0;
}


#笔试题目##题解#
全部评论
感觉就是leetcode岛屿数量,dfs就完事了
4 回复
分享
发布于 2021-01-17 12:41
这不是搜索的套路题吗 直接扫描每个格子,如果是t就bfs或者dfs,把所有相邻的t全部标记为b,搜索完成后ans➕➕,最后输出答案即可
3 回复
分享
发布于 2021-01-17 10:05
饿了么
校招火热招聘中
官网直投
void dfs(char **map, int n, int i, int j) {     char *c = (char *)map + i * n + j; //当前     char *c_up = (char *)map + (i-1) * n + j ; //上     char *c_down = (char *)map + (i+1) * n + j ;//下     char *c_left = (char *)map + i * n + j - 1;//左     char *c_right = (char *)map + i * n + j + 1;//右     *c = 'B&(3582)#39;;     if(i-1 >= 0 && *c_up == 'T&(3581)#39;)         dfs(map, n, i-1, j);     if(i+1 < n && *c_down == 'T&(3581)#39; )         dfs(map, n, i+1, j);     if(j-1 >= 0 && *c_left == 'T&(3581)#39;)         dfs(map, n, i, j-1);     if(j+1 < n && *c_right == 'T&(3581)#39;)         dfs(map, n, i, j+1); } int count(char **map, int n) {     int count = 0;     for(int i = 0; i < n; i++){         for(int j = 0; j < n; j++){             char *c = (char *)map + i * n + j; //当前             if(*c == 'T&(3581)#39;){                 count++;                 dfs2(map, n, i, j);             }         }     }     return count; }
点赞 回复
分享
发布于 2021-01-17 19:05

相关推荐

点赞 4 评论
分享
牛客网
牛客企业服务