P1003 su_starry的西双版纳之旅

一.解题思路

1.碎碎念

好像没啥好说的，那就吐槽一下社长编背景编的挺粗制滥造吧，希望P1005能有一个让人眼前一亮的背景（编背景你就给我编好了啊！

2.题目分析

看题的话是一道比较常规的最大岛屿问题，那么思路就很清晰了，DFS/BFS都行，看自己想法了（n,m均在50以内，DFS应该没问题，不过我没试过，用DFS的小伙伴可以说一下）

不过我一开始想的是在输入每一行数据时直接标记1所在的位置，然后记录这一行的最大岛屿，再输入下一行时判断能否和上一行相连，可以的话就继续叠，同时更新最大值，不过自己写了几步就碰到了点麻烦，能力有限写不出来这个思路，后面问ai说是并查集（或许吧因为我压根不会这个）呜呜呜还是太菜了😭😭😭

3.算法实现

那么好，既然选择用更常规的BFS来写，那就啥也别说了，直接套模版！（嘻嘻嘻

1.我们现在要做的就是遍历每个格子，当其为1【陆地】时，我们将这个格子存入队列，并将它改成0【海洋】（这样做是为了防止重复遍历）

2.然后只要队列不为空，我们就把这个队列存的格子取出来，然后让其出队，并且面积加一

3.接着判断四个方向上的格子是否合法，合法就入队，然后重复2，3的操作

4.最后更新最大ans就行了！

4.复杂度

1.时间：O(nm)

2.空间：O(nm)

二.完整代码

PS：非专业题解！有任何错误记得联系我！！！