登录
  • #刷题

13‌‌‍‍‌‍‍‌‍‌‍‍‌‌‌‍‍‌‌‌‌‌‍‍‍‌‌‌‍‍‍‌0. Surrounded Regions 检查N久不知道写的代码哪里有问题,运行不通过。。。。。。

ATPtennis
210
11
我找到一个代码共享黏贴网站,大家直接在这里看吧,真的好方便。paste.ubuntu.com

这道题虽然运行错了,但是我仍然有2个疑惑点。

1,那个board[x][y] = "T" 我想了半天到底放哪,为了保险,我就放在立刻popleft后面了,因为可能后面找完邻居,我下面已经把邻居变T了,然后popleft出来以后,再刷上一遍T,也没事。这个 board[x][y] = "T" 必须写的原因是因为我要保证第一个边界O变T,没有这个第一个O无法变T,而是从邻居开始变T的。等于开头的起始位置变不了T了。

2,这题思路我是仿照 200. Number of Islands做的,因为孤岛这题BFS是紧跟在遍历出第一个元素后的,也就是队列里起始就一个元素。然后把相邻的都刷成别的数,孤岛这题需要记录的只是刷完一个大块后的次数,所以起始位置是什么不用管。刷完一大块后,然后找隔离的另一块刷。而这个XO题,我也是开始遍历边界第一个O点以后,然后也是顺着搞完一片再执行第二个隔离的O点。我想思路应该没错。

个人理解,要不要把BFS写在遍历第一个元素后,还是另起一行写在完成遍历后,取决于这道题要什么。994. Rotting Oranges烂橘子那道题要求的是经过几次全变烂,这时候你如果紧跟着写在遍历出第一个元素后,他就把一片都感染了,你统计不了次数。孤岛这道题你如果按烂橘子那样,BFS写在遍历结束后,你就统计的数太多了,人家只是把一片算一个。你一层一层的统计了一堆数出来,不是题目想要的。

而这道XO题,我觉得两种方法均可,因为这道题不要求你统计次数,只是让你把一片找出来,所以有点类似孤岛,我就采取了孤岛的紧跟在第一个遍历出的元素后面写的BFS。不知道错误跟这有没有关系。

忘解惑,谢谢!卡了很久。
11条回复
热度排序

发表回复