hiho一下第156周《Counting Islands》题目分析

0
0

《岛屿》题目分析

本题是一道非常经典的2D地图上的搜索问题，类似的问题还包括走迷宫、求房间数目等。

这道题需要我们求出三个数值，一是海岛数目，二是面积不同的海岛数目，三是形状不同的海岛数目。

第一个小问题是最基本的搜索问题。

一般我们可以从上到下、从左到右扫描，直到发现一个没有处理过的'#'。然后从这个'#'开始沿着4个方向扩展，把连在一起的'#'都找出来。这些连在一起的'#'就组成一个岛屿。

伪代码如下，当然用bfs代替dfs也是没问题的：

for i = [0 .. N):
    for j = [0 .. M):
        if NOT visited[i][j] AND grid[i][j] == '#':
            dfs(i, j)

dfs(i, j):
    int dx[4] = {-1, 1, 0, 0}
    int dy[4] = {0, 0, -1, 1}
    visited[i][j] = true
    for d = [0 .. 4):
        int _x = i + dx[d]
        int _y = j + dy[d]
        if (_x, _y) is inside the boarder AND NOT visited[_x][_y] AND grid[_x][_y] == '#':
            dfs(_x, _y)

第二个小问题很容易就可以在第一个小问题的基础上求得。我们只需在dfs/bfs找岛屿的过程中保存一下'#'的数目即可。

第三个小问题判断形状相同，我们可以用相对位置来判断。

以样例数据为例，第一行的"####"对应的坐标(行从上到下，列从左到右)依次是(0, 1)(0, 2)(0, 3)(0, 4)。如果我们以其先最上其次最左的点，也就是(0, 1)为基准的话，相对位置序列是(0, 0)(0, 1)(0, 2)(0, 3)。

同理第三行的"####"的坐标依次是(2, 0)(2, 1)(2, 2)(2, 3)，其相对位置也是(0, 0)(0, 1)(0, 2)(0, 3)。两个岛屿形状相同，当且仅当它们的相对位置序列完全相同。

所以我们需要在dfs/bfs找岛屿的过程中把陆地的位置都保存下来。

值得一提的是如果我们按照确定的顺序搜索陆地，（例如以上代码中先行后列扫描第一块陆地，同时在dfs中保持按上下左右的顺序扩展陆地）那么对于两个形状相同的岛屿，我们求出的坐标序列恰好就是一一对应的。

如果我们还不放心，可以将坐标序列重新排序之后，再选择第一个坐标为基准点，求出相对位置序列。

11 answer(s)

0

如果要考虑旋转位置的情况，可以比较两个形状的时候，对其中一个形状进行旋转，选择（0,0）作为基准点，形状内的所有点分别旋转90°，旋转三次。

0

本题好像没有考虑旋转后形状相同的情况。

0

def get_map(): map = [[0, 0, 0, '#', 0], ['#', '#', 0, '#', 0], [0, 0, '#', 0,'#'], [0, '#', '#', 0, '#']] return map

def gone(island_shape, island_area, map, x, y, has_gone_list): #在这个岛屿上游走开发 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]

for i in range(4):
    move_x = x + dx[i]
    move_y = y + dy[i]
    if 0 <= move_x <= 3 and 0 <= move_y <= 4:
        if map[move_x][move_y] == '#' and (move_x, move_y) not in has_gone_list:
            has_gone_list.append((move_x, move_y))
            island_shape.append([dx[i],dy[i]])
            island_area += 1
            island_shape, island_area, has_gone_list = gone(island_shape, island_area, map, move_x, move_y,has_gone_list)

return island_shape, island_area, has_gone_list

def get_island_num(map): island_num = 0 island_area_list = [] island_shape_list = [] rows = len(map) colomns = len(map[0]) has_gone_list = [] for i in range(rows): for j in range(colomns): if map[i][j] == '#' and (i,j) not in has_gone_list: #是岛屿并且没有被开发 island_num += 1 has_gone_list.append((i,j)) island_area = 1 island_shape = [] island_shape, island_area, has_gone_list = gone(island_shape, island_area, map, i, j, has_gone_list) #在这个岛屿上进行开发游走 island_area_list.append(island_area) island_shape_list.append(island_shape)

return island_num, island_area_list, island_shape_list

if name == "main": map = get_map() island_num, island_area_list, island_shape_list = get_island_num(map) print("一共有{0}个岛屿".format(island_num)) #print("面积分别为：{0}".format(island_area_list)) print("面积不同的岛屿数目：{0}".format(len(set(island_area_list)))) island_shape_list_tmp = [] shape_uni_num = 0 for item in island_shape_list: if item not in island_shape_list_tmp: shape_uni_num += 1 island_shape_list_tmp.append(item) print("不同形状岛屿的数目：{0}".format(shape_uni_num))

0

我觉得好坑啊，Javaer怎么办，一次性AC的，但是java1.8改成1.7语法，编译报错了4次。。

0

有没有陷阱呀，我的通过了50%

0

直接对岛屿hash判不同形状个数，也过了。。。

0

输入测试的5×7地图答案是对的，但...交上去之后是WA。 求帮助，代码如下：

enter code here
vector<vector<int>> P,Q;
int N,M;
int sum;
vector<int> area;//面积数组
vector<string> shape;//形状数组
string str;//用于记录地图形状
int * cur_area = new int;//面积

void FindIsland(int x, int y, int type)//type是起始点或上下左右
{
if(x>=N || x <0 || y>=M || y<0) return;//越界不处理
if(P[x][y] == 1 && Q[x][y] == 0)//是陆地且未探索
{
    switch (type)
    {
    case 1://下
        str=str + 'x';
        break;
    case 2://右
        str = str + 'r';
        break;
    case 3://上
        str = str + 's';
        break;
    case 4://左
        str = str + 'z';
        break;
    default:str="";//起始点清空记录
        break;
    }
    (*cur_area)++;//面积加一
    Q[x][y] = 1;//此点探索过
    FindIsland(x+1,y,1);//下探索
    FindIsland(x,y+1,2);//右探索
    FindIsland(x-1,y,3);//上探索
    FindIsland(x,y-1,4);//左探索
}
}

int main()
{
str = "";
*cur_area = 0;
sum =0;
char ch;
cin >> N >> M;//输入行数列数
P.resize(N);//重新分配行数P是岛的地图
Q.resize(N);//Q是是否检测过
for(int x =0;x < N;x++)
{
    P[x].resize(M);//重新分配列数
    Q[x].resize(M);
    for(int y =0;y < M;y++)
    {
        cin >> ch;//XY坐标下的形状.或#
        if(ch == '.') P[x][y] = 0;//海是0
        else P[x][y] = 1;//地是1
        Q[x][y] = 0;//没探索过
    }
}

for(int x =0;x < N;x++)
    for(int y = 0;y<M;y++)
    {
        if(P[x][y] == 1 && Q[x][y] == 0) //是陆地且没探索过
        {
            sum++;//岛的数量增加1
            *cur_area = 0;//当前面积为0
            FindIsland(x,y,0);//拓展
            vector<int>::iterator it = find(area.begin(),area.end(),*cur_area);
            if(it == area.end()) area.push_back(*cur_area);//面积不曾有过，入栈
            vector<string>::iterator its = find(shape.begin(),shape.end(),str);
            if(its == shape.end()) shape.push_back(str);//形状不曾有过进栈
        }
    }
cout << sum << " " << area.size() << " " << shape.size();
return 0;
}
enter code here
2

求一个测试的案例啊

0

How to judge if two connected areas are in the same shape if rotation is also allowed?

  • 如果是90度rotate的话，比较容易，把相差的坐标记下来 ，来个四次循环遍历就行了

  • 好像还有一些细节要考虑

  • 旋转 可以有4种情况，每个反转以后还有四种情况

  • 添加评论
  • ✖reply
0

这次的题目描述中出现了几个错别字，把“海岛”打成了“海盗”，输入描述里面“两个人整数”等。

4

哇还没有题目就能看题解了

write answer 切换为英文 切换为中文

转发分享

▲