@ninijia 在 Leetcode每日一题练习 ------ 2257. 统计网格图中没有被保卫的格子数 中发帖
从Leetcode 每日一题练习继续讨论:
2257. 统计网格图中没有被保卫的格子数
2257. Count Unguarded Cells in the Grid
题解
本题模拟守卫能看到的区域,首先创建mxn的数组,先遍历所有墙的位置将对应位置的值设置为2,记录墙的个数,再遍历守卫,对每个守卫所在的位置向四个方向遍历直到到数组边界或者遇到墙为止,将这些位置的值设置为1,同时记录遍历过程中将0变为1的个数,最终用数组总数减去墙和守卫以及守卫看守的位置数的和得最终结果。
这种遍历并且按照属性设置对应位置的值的方法可以得到正确的结果,但对有些示例会超时,思考为什么会超时以及如何优化,可以想到如果从某个守卫出发开始向某一方向(比如向右)遍历数组时遇到了另一个守卫,起始没有必要再继续向该方向遍历了,因为后面的位置遇到的新守卫同样也可以看到,此时可以直接结束遍历,因此我们可以将墙的位置值...