高级编程通关练习题 #3 – 矩阵围城

给定一个 m x n 字符串矩阵,m 和 n 都大于 3。矩阵里的每一个元素都是一个字母,检查是否有相同字母在矩阵里面形成一个围城。如下图所示,字母 a 在这个 7 x 5 的矩阵里面形成了一个围城。

matrix cycle

输入样例:

grid = [
[“a”, “a”, “a”, “a”, “a”, “b”, “b”],
[“a”, “c”, “c”, “c”, “a”, “a”, “a”],
[“a”, “b”, “b”, “b”, “c”, “c”, “a”],
[“a”, “a”, “a”, “a”, “b”, “b”, “a”],
[“b”, “b”, “b”, “a”, “a”, “a”, “a”]
]

输出样例:

True

算法思路:

  • 循环矩阵里的每一个元素,检查它的周围元素是否有相同字母。如果有就采用递归方法继续搜索。
  • 遍历矩阵时,每次检查一个元素都把它加入到已经检查过的缓存列表里面。
  • 在递归搜索时,如果发现同一个元素最终可以找到已经检查过的元素,则表明找到了一个围城。