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

卫星拍摄的地面遥感图像是一个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;
}

#笔试题目##题解#

全部评论

推荐最新楼层

RamseyX

腾讯_csig 腾讯会议_后端开发

感觉就是leetcode岛屿数量，dfs就完事了

4 回复分享

发布于 2021-01-17 12:41

合情合理

字节跳动_抖音_Android

这不是搜索的套路题吗直接扫描每个格子，如果是t就bfs或者dfs，把所有相邻的t全部标记为b，搜索完成后ans➕➕，最后输出答案即可

3 回复分享

发布于 2021-01-17 10:05

胖虎不吃小孩

楼主

湖南大学 Java

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