美团笔试题

昨天做了下美团的KPI笔试，问：

思路：DFS

需要一个visited数组存放遍历每条路径已经访问过的节点

代码：

n, m = map(int, input().split())
a = []
for _ in range(n):
  a.append(list(input()))

  s = ['A', 'B', 'C', 'D', 'E']
  visited = []


  def dfs(i, j, res=0):
	if a[i][j] == s[(res) % 5] and (i, j) not in visited:
	  print(i, j, s[res % 5])
	  visited.append((i, j))
	  res += 1
	  for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
		if 0 <= x <= n - 1 and 0 <= y <= m - 1 and (x, y) not in visited:
		  res = dfs(x, y, res)
		  return res

ans = []
for i in range(n):
	for j in range(m):
		if a[i][j] == "A":
			 res = dfs(i, j, 0)
			 visited = []
			 ans.append(res)

print(max(ans))