解题思路:
先找到坦克的起始点,用变量记录下来。用广搜 -dfs的方式解决。
题的目标:最少移动步数数 有则输出无则输出-1
dfs的技巧:
先开栈避免因数据规模太大递归次数太多而出现爆栈的情况,分不清是记忆化搜索还是不是记忆化搜索那就直接写上lru_cache(maxsize=None)
分析:
坦克只能是所在位置与下一个位置不同时才能行走所以要判断Map[xx][yy]是否与Map[x][y]相等,相等要跳过,不相等给走过的位置打商标机然后dfs(xx,yy,depth+1) 最后再清除标记。
坦克可以上下左右移动所以要设置一个移动数组dirt = [[0, 1], [0, -1], [1, 0], [-1, 0]]遍历数组代表了向四周移动,注意要判断边界
注意事项:
标记数组一定要用列表推导式写,不然会出错,具体原因我也不知道
参考代码:
from functools import lru_cache
import sys
#明天来了给走过的路径打标记,回去睡觉
sys.setrecursionlimit(1000000)
@lru_cache(maxsize=None)
def dfs(x, y, depth):
global ans
if depth > ans:
return
if x == x2 and y == y2:
ans = min(ans, depth)
return
for i in range(4):
xx = x + dirt[i][0]
yy = y + dirt[i][1]
if 0 <= xx < n and 0 <= yy < n:
if vis[xx][yy]==True:
continue
if Map[xx][yy] != Map[x][y]:
vis[xx][yy]=True
dfs(xx, yy, depth + 1)
vis[xx][yy]=False
n = int(input())
Map = []
for i in range(n):
Map.append(list(input().split()))
x1, y1, x2, y2 = 0, 0, 0, 0
for i in range(n):
for j in range(n):
if Map[i][j] == "A":
x1 = i
y1 = j
if Map[i][j] == 'B':
x2 = i
y2 = j
dirt = [[0, 1], [0, -1], [1, 0], [-1, 0]]
vis=[[False]*n for _ in range(n)]
#bi标记数组一定要用推导式写,不然会出现错误
#vis=[[False]*n]*n
ans = 10000000000
dfs(x1,y2,0)
if ans==10000000000:
ans=-1
else:
ans
print(ans)
0.0分
0 人评分
IP判断 (C++代码)浏览:677 |
大神老白 (C语言代码)浏览:715 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:664 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1053 |
小明A+B (C语言代码)浏览:1256 |
剪刀石头布 (C语言代码)浏览:1755 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:635 |
Hello, world! (C语言代码)浏览:824 |
GC的苦恼 (C语言代码)浏览:621 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:648 |