[已解决]Python：每日一题 327

zltzlt

今天的题目：

给定一个二维数组，代表地图。
其中 'S' 表示起点，'T' 表示终点。'#' 代表墙壁，无法通过，'.' 表示普通的路，需要花一分钟时间通过。

求从起点到终点需要花费的最短时间（以分钟为单位）。如果无法到达终点则输出 -1。

示例 1：

输入：
[
  ['S', '.'],
  ['#', 'T']
]
输出：2
解释：S --> . --> 向右转，走到 T。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

William4869

2020-2-8 19:23:05

1. def f327(x):
   
2.     dp=[[]for i in range(len(x))]
   
3.     que=[[]]
   
4.     gox=[1,0,-1,0]
   
5.     goy=[0,1,0,-1]
   
6.     for i in range(len(x)):
   
7.         for j in range(len(x[0])):
   
8.             dp[i].append(-1)
   
9.             if x[i][j]=='S':
   
10.                 dp[i][j]=0
    
11.                 que[0].append(i)
    
12.                 que[0].append(j)
    
13.             if x[i][j]=='T':
    
14.                 retx=i
    
15.                 rety=j
    
16.     while len(que):
    
17.         p=que.pop(0)
    
18.         if p[0]==retx and p[1]==rety:
    
19.             break
    
20.         for i in range(4):
    
21.             nx=p[0]+gox[i]
    
22.             ny=p[1]+goy[i]
    
23.             if nx>=0 and nx<len(x) and ny>=0 and ny<len(x[0])\
    
24.                and x[nx][ny]!='#' and \
    
25.                (dp[nx][ny]>(dp[p[0]][p[1]]+1)or dp[nx][ny]==-1) :
    
26.                 que.append([nx,ny])
    
27.                 dp[nx][ny]=dp[p[0]][p[1]]+1
    
28.    # print(dp)
    
29.     return dp[retx][rety]
    

复制代码

BFS搜索，，，应该没什么问题

跳转到最佳答案楼层

William4869

1. def f327(x):
   
2.     dp=[[]for i in range(len(x))]
   
3.     que=[[]]
   
4.     gox=[1,0,-1,0]
   
5.     goy=[0,1,0,-1]
   
6.     for i in range(len(x)):
   
7.         for j in range(len(x[0])):
   
8.             dp[i].append(-1)
   
9.             if x[i][j]=='S':
   
10.                 dp[i][j]=0
    
11.                 que[0].append(i)
    
12.                 que[0].append(j)
    
13.             if x[i][j]=='T':
    
14.                 retx=i
    
15.                 rety=j
    
16.     while len(que):
    
17.         p=que.pop(0)
    
18.         if p[0]==retx and p[1]==rety:
    
19.             break
    
20.         for i in range(4):
    
21.             nx=p[0]+gox[i]
    
22.             ny=p[1]+goy[i]
    
23.             if nx>=0 and nx<len(x) and ny>=0 and ny<len(x[0])\
    
24.                and x[nx][ny]!='#' and \
    
25.                (dp[nx][ny]>(dp[p[0]][p[1]]+1)or dp[nx][ny]==-1) :
    
26.                 que.append([nx,ny])
    
27.                 dp[nx][ny]=dp[p[0]][p[1]]+1
    
28.    # print(dp)
    
29.     return dp[retx][rety]
    

复制代码

BFS搜索，，，应该没什么问题

一个账号

能不能给多点示例？

阴阳神万物主

最短路径搜索啊，我想一想。
话说，有地图循环的设计吗？
比如：

1. 输入:
   
2.         [['S','#','T']]
   
3. 输出:
   
4.         1

复制代码

塔利班

1. def f327(x):
   
2.     a,b=len(x),len(x[0])
   
3.     def dp(i,j,s,l):
   
4.         if i in range(a) and j in range(b):
   
5.             if x[i][j] in l:
   
6.                 return a*b
   
7.             else:
   
8.                 l.add((i,j))
   
9.             if x[i][j]=='T':
   
10.                 return s
    
11.             elif x[i][j] in 'S.':
    
12.                 ps={(i+1,j),(i-1,j),(i,j+1),(i,j-1)}
    
13.                 return min([dp(ii,jj,s+1,l.copy()) for ii,jj in ps-l])
    
14.             else:
    
15.                 return a*b
    
16.         else:
    
17.             return a*b
    
18. 
    
19.     for i in range(a):
    
20.         for j in range(b):
    
21.             if x[i][j]=='S':
    
22.                 res=dp(i,j,0,set())
    
23.                 return -1 if res>=a*b else res

复制代码

最近有点愚笨，先来踩雷

Croper

A*算法

1. class SortedList(list):
   
2.     def __init__(self,key=lambda x:x):
   
3.         super().__init__();
   
4.         self.key=key
   
5.         self.reversed=reversed
   
6.         
   
7.     def append(self,ele):
   
8.         p,q=0,len(self)
   
9.         while p<q:
   
10.             n=(p+q)//2
    
11.             if self.key(ele)>self.key(self[n]):
    
12.                 q=n
    
13.             else:
    
14.                 p=n+1
    
15.         super().insert(p,ele)
    
16. 
    
17. def func327(map):
    
18.     if len(map)==0 or len(map[0])==0:
    
19.         return -1;
    
20.     start_pos=target_pos=None;
    
21.     for i in range(len(map)):
    
22.         for j in range(len(map[i])):
    
23.             if map[i][j]=='S':
    
24.                 map[i][j]=0
    
25.                 start_pos=(i,j)
    
26.             if map[i][j]=='T':
    
27.                 target_pos=(i,j)
    
28. 
    
29. 
    
30.     def valid(pos:tuple):
    
31.         return 0<=pos[0]<len(map) and 0<=pos[1]<len(map[pos[0]])
    
32. 
    
33.     offset=((1,0),(-1,0),(0,1),(0,-1))
    
34.     inner=[]
    
35.     outer=SortedList(key=lambda x:abs(x[0]-target_pos[0])+abs(x[1]-target_pos[1])+map[x[0]][x[1]])
    
36. 
    
37.     outer.append(start_pos)
    
38. 
    
39.     while len(outer)>0:
    
40.         #printl2(map)
    
41.         #print()
    
42.         #for i in outer:
    
43.             #print(map[i[0]][i[1]],end=" ")
    
44.         #print()
    
45.         #time.sleep(0.5)
    
46.         pos=outer.pop();
    
47.         inner.append(pos)
    
48.         n=map[pos[0]][pos[1]]
    
49. 
    
50.         for i in range(4):
    
51.             y,x=pos[0]+offset[i][0],pos[1]+offset[i][1]
    
52.             if valid((y,x)):
    
53.                 if (y,x) in inner:
    
54.                     continue
    
55.                 c=map[y][x]
    
56.                 if c=='T':
    
57.                     return n+1
    
58.                 if c=='.':
    
59.                     map[y][x]=n+1
    
60.                     outer.append((y,x))
    
61.                
    
62.     return -1

复制代码

TJBEST

前排占个楼。已有思路，11点前调试发送

William4869

可以多给几个样例调试吗，写的差不多了，不知道对不对

546623863

最小路径算法。。。。。。当初学java的时候最头疼这玩意了

zltzlt

阴阳神万物主 发表于 2020-2-8 20:20
最短路径搜索啊，我想一想。
话说，有地图循环的设计吗？
比如：

输出 -1，不是 1

zltzlt

塔利班 发表于 2020-2-8 20:33
最近有点愚笨，先来踩雷

输入 [['.', 'T', '.', 'S', '.', '#', '.', '.', '.', '.'], ['#', '.', '.', '.', '.', '#', '.', '#', '.', '.'], ['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'], ['.', '.', '.', '.', '#', '#', '.', '.', '.', '.'], ['#', '#', '.', '.', '.', '.', '.', '#', '.', '#']] 出错

塔利班

zltzlt 发表于 2020-2-8 21:58
输入 [['.', 'T', '.', 'S', '.', '#', '.', '.', '.', '.'], ['#', '.', '.', '.', '.', '#', '.', '#', ...

1. 
   
2. def f327(x):
   
3.     a,b=len(x),len(x[0])
   
4.     def dp(i,j,s,l):
   
5.         if i in range(a) and j in range(b):
   
6.             if x[i][j] in l:
   
7.                 return a*b
   
8.             else:
   
9.                 l.add((i,j))
   
10.             if x[i][j]=='T':
    
11.                 return s
    
12.             elif x[i][j] in 'S.':
    
13.                 ps={(i+1,j),(i-1,j),(i,j+1),(i,j-1)}
    
14.                 return min([dp(ii,jj,s+1,l.copy()) for ii,jj in ps-l]+[a*b])
    
15.             else:
    
16.                 return a*b
    
17.         else:
    
18.             return a*b
    
19. 
    
20.     for i in range(a):
    
21.         for j in range(b):
    
22.             if x[i][j]=='S':
    
23.                 res=dp(i,j,0,set())
    
24.                 return -1 if res>=a*b else res

复制代码

zltzlt

Croper 发表于 2020-2-8 20:52
A*算法

输入：

1. [['.', '#', '.', '.', '#', '.', '.', '.', '.', '#', '.', '#'], ['.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '#', '#', '#', '#', '#', 'S', '.', '.'], ['#', '#', '.', '#', '.', '#', '.', '.', '#', '#', '.', '.'], ['.', '#', '.', '.', '.', '#', '#', '#', '.', '#', '#', '.'], ['.', '.', '#', '.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '#', '.', '#', '#', '#', '.', '.', '.', '.', '.'], ['.', '#', '.', '#', '#', '#', '.', '#', '.', '#', '.', '.'], ['#', '.', '.', '.', '#', '.', '.', '#', '.', '#', '#', '.'], ['.', '.', '#', '#', '#', '.', '#', '#', '.', '.', '.', '.'], ['#', '.', '#', '#', '.', '.', '#', '#', '#', '.', '#', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#', '.'], ['#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '#'], ['#', '.', '#', '#', '#', 'T', '.', '#', '#', '.', '.', '#'], ['.', '#', '#', '#', '.', '#', '.', '.', '.', '#', '.', '.'], ['#', '.', '.', '.', '.', '#', '.', '#', '#', '.', '.', '.']]

复制代码

输出：23
预期结果：21

zltzlt

William4869 发表于 2020-2-8 21:50
BFS搜索，，，应该没什么问题

解答错误

输入：

1. [['.', '#', '.', '#', '#', '.'], ['.', '#', 'S', '.', '#', '.'], ['.', '#', '.', '#', '#', '#'], ['.', '.', '#', '.', '#', '.'], ['.', '.', '.', '.', '.', '.'], ['.', '#', 'T', '.', '.', '.']]

复制代码

输出：99999
预期结果：-1

裤裆里面有杀气

学到零基础35课时，表示题目看不懂。。。

zltzlt

塔利班 发表于 2020-2-8 22:01

输入以下数据超时：

1. [['.', '.', '#', '#', '.', '#', '#', '.', '#', '#'], ['#', '.', '.', '#', '.', '.', '.', '#', '#', '#'], ['.', '.', '.', '.', '.', '.', '.', '#', '#', '#'], ['.', '#', '#', '.', '#', '.', '.', '.', '.', '#'], ['.', '.', '#', '#', '.', '.', '#', '#', '#', '.'], ['.', '.', '#', '.', '.', '#', '.', '.', '.', '.'], ['.', '.', '#', '.', '.', '.', '#', '.', '.', '.'], ['#', '.', '.', '.', '.', '#', '.', '.', '.', '#'], ['.', '.', '.', 'S', 'T', '.', '.', '#', '.', '.'], ['.', '.', '.', '#', '.', '#', '.', '#', '#', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.']]

复制代码

William4869

William4869 发表于 2020-2-8 21:50
BFS搜索，，，应该没什么问题

说一下大概步骤，先整一个同样大小的矩阵，值置为-1，S那一点的值置为0，T的横纵坐标先保存

对输入的二维数组x 从S开始用BFS搜索
之前先定义好了gox，goy，代表了下一步会怎么走，每一个点开始有4种走法，要是下一点可以走，并且没有访问过，让点进队，那个点对应的dp值置为上一步的值+1，直到搜到T点位置，
本来想整一个visit数组的，后来想想，只要遇到的数字不比本身数字大1以上，就是没访问过的点了，

再仔细想想，好像值为-1就是没访问过得点，程序也懒得改了。

TJBEST

楼主测测吧，可能超时

1. def fun327(path_map):
   
2.     #x是行号 y是列号
   
3.     M = len(path_map)
   
4.     N = len(path_map[0])
   
5.     path_possible = []#所有的'.'
   
6.     for x in range(0,M):
   
7.         for y in range(0,N):
   
8.             if path_map[x][y] == '.':
   
9.                 path_possible.append((x,y))
   
10.             elif path_map[x][y] == 'S':
    
11.                 S = (x,y)
    
12.             elif path_map[x][y] == 'T':
    
13.                 T = (x,y)
    
14.     index = 1            
    
15.     tempset={S}#最低步数为index-1的 坐标集合
    
16.     path_possible.append(T)#终点也加入
    
17. 
    
18.     while True:
    
19.         mySet = set()
    
20.         for centerPoint in tempset:
    
21.             if centerPoint[0] > 0:#up
    
22.                 tempPoint = (centerPoint[0] - 1,centerPoint[1])
    
23.                 if tempPoint in path_possible:
    
24.                     mySet.add(tempPoint)
    
25.                     path_possible.remove(tempPoint)
    
26.             
    
27.             if centerPoint[0] < M - 1:#down
    
28.                 tempPoint = (centerPoint[0] + 1,centerPoint[1])
    
29.                 if tempPoint in path_possible:
    
30.                     mySet.add(tempPoint)
    
31.                     path_possible.remove(tempPoint)
    
32. 
    
33.             if centerPoint[1] > 0:#left
    
34.                 tempPoint = (centerPoint[0],centerPoint[1] - 1)
    
35.                 if tempPoint in path_possible:
    
36.                     mySet.add(tempPoint)
    
37.                     path_possible.remove(tempPoint)
    
38. 
    
39.             if centerPoint[1] < N - 1:#right
    
40.                 tempPoint = (centerPoint[0],centerPoint[1] + 1)
    
41.                 if tempPoint in path_possible:
    
42.                     mySet.add(tempPoint)
    
43.                     path_possible.remove(tempPoint)
    
44. 
    
45.         if T in mySet:
    
46.             return index
    
47.         elif mySet == set():
    
48.             return -1
    
49.         else:
    
50.             index = index + 1
    
51.             tempset = mySet

复制代码

zltzlt

TJBEST 发表于 2020-2-8 22:08
楼主测测吧，可能超时

确实会超时哦

TJBEST

zltzlt 发表于 2020-2-8 22:09
确实会超时哦

数对吗？