题目83：允许向上下左右移动的情况下从左上角到右下角的最小路径和是多少？

欧拉计划

Path sum: four ways

NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

题目：

注意：该题目是题目 81 的一个更难的版本。

在以下这个 5×5 的矩阵中，在允许向上，下，左，右移动的情况下，从左上角到右下角的最小路径和是 2297。路径用红色标出。

p083_matrix.txt (30.57 KB, 下载次数: 18)

2016-8-9 17:09 上传

点击文件名下载附件

包含一个 80×80 的矩阵，在允许向上，下，左，右移动的情况下，找出从左上角到右下角的最小路径和。

jerryxjr1220

1. a=[[0 for i in range(85)]for j in range(85)]
   
2. dp=[[999999999 for i in range(85)]for j in range(85)]
   
3. vis=[[0 for i in range(85)]for j in range(85)]
   
4. tot=0
   
5. way=[]
   
6. Mini=-1
   
7. Minj=-1
   
8. Min=9999999999
   
9. dx=[1,-1,0,0]
   
10. dy=[0,0,1,-1]
    
11. 
    
12. def find():
    
13.     global Mini
    
14.     global Minj
    
15.     global Min
    
16.     Mini=-1
    
17.     Minj=-1
    
18.     Min=9999999999
    
19.     for w in range(len(way)):
    
20.         i=way[w][0]
    
21.         j=way[w][1]
    
22.         for k in range(4):
    
23.             nx=i+dx[k]
    
24.             ny=j+dy[k]
    
25.             if nx>=0 and nx<80 and ny>=0 and ny<80 and vis[nx][ny]==0 and dp[i][j]+a[nx][ny]<Min:
    
26.                 Min=dp[i][j]+a[nx][ny]
    
27.                 Mini=nx
    
28.                 Minj=ny
    
29. 
    
30. def update():
    
31.     global tot
    
32.     global Min
    
33.     x=Mini
    
34.     y=Minj
    
35.     dp[x][y]=Min
    
36.     vis[x][y]=1
    
37.     way.append([x,y])
    
38.     tot+=1
    
39.     print('第',tot,'个节点确定：(',x,',',y,')')
    
40.     if x==79 and y==79:
    
41.         return True
    
42.     else:
    
43.         return False
    
44. 
    
45. file=open('matrix.txt')
    
46. f=file.read()
    
47. file.close()
    
48. s=f.split('\n')
    
49. for i in range(80):
    
50.     a[i]=s[i].split(',')
    
51. for i in range(80):
    
52.     for j in range(80):
    
53.         a[i][j]=int(a[i][j])
    
54. vis[0][0]=1
    
55. dp[0][0]=a[0][0]
    
56. tot+=1
    
57. way.append([0,0])
    
58. while tot<6400:
    
59.     find() #找到最小的位置
    
60.     if update()==True: #更新
    
61.         break
    
62. print('bingo: ',dp[79][79])

复制代码

bingo:  425185

jerryxjr1220

思路和上述方法一致，但是简化了算法，时间缩短了10倍

1. #coding:utf-8
   
2. #initiate:
   
3. file=open('matrix.txt')
   
4. f=file.read()
   
5. file.close()
   
6. s=f.split('\n')
   
7. matrix = [[]*80 for i in range(80)]
   
8. for i in range(80):
   
9.     matrix[i]=s[i].split(',')
   
10. for i in range(80):
    
11.     for j in range(80):
    
12.         matrix[i][j]=int(matrix[i][j])
    
13. 
    
14. visited = [[False]*80 for i in range(80)]
    
15. dp = [[999999]*80 for i in range(80)]
    
16. move = [(1,0),(-1,0),(0,1),(0,-1)]
    
17. checklist = [(0,0)]
    
18. dp[0][0] = 4445
    
19. 
    
20. #define the method for searching the best way:
    
21. def findway(x,y):
    
22.         if not visited[x][y]:
    
23.                 visited[x][y] = True
    
24.                 for m in move:
    
25.                         nx,ny = x+m[0],y+m[1]
    
26.                         if 0<=nx<80 and 0<=ny<80:
    
27.                                 dp[nx][ny] = min(dp[x][y]+matrix[nx][ny],dp[nx][ny])
    
28.                                 checklist.append((nx,ny))
    
29. 
    
30. #min7979 is the min price to go:
    
31. min7979 = 999999
    
32. 
    
33. #repeat again and again until the min is stable, that's the answer.
    
34. while True:
    
35.         for i in range(len(checklist)):
    
36.                 findway(checklist[i][0],checklist[i][1])
    
37.         if len([(j,k) for j in range(80) for k in range(80) if not visited[j][k]]) == 0:
    
38.                 visited = [[False]*80 for i in range(80)]
    
39.                 checklist = [(0,0)]
    
40.                 if min7979 > dp[79][79]:
    
41.                         min7979 = dp[79][79]
    
42.                 else:
    
43.                         print (min7979)
    
44.                         break

复制代码

425185
[Finished in 3.8s]

najin

用的matlab
结果是：
ans =

      425185

时间已过 0.433833 秒。
路径用matlab可以动态画出来
可惜不能上传图片

JAY饭

1. import shuzimigong as sh
   
2. 
   
3. t = sh.t.split('\n')
   
4. s = [[] for i in range(80)]
   
5. for i in range(80):
   
6.     for each in  t[i].split(','):
   
7.         s[i].append(int(each))
   
8. 
   
9. 
   
10. right = {(0,0):s[0][0]}
    
11. right1 = {}
    
12. t = [(-1,0),(1,0),(0,1),(0,-1)]
    
13. 
    
14. def move():
    
15.     count = s[0][0]
    
16.     a = 0
    
17.     b = 0
    
18.     while True:
    
19.         if a == 79 and b == 79:
    
20.             break
    
21.         if a == 79 and b != 79:
    
22.             count += s[a][b+1]
    
23.             b += 1
    
24.         elif a != 79 and b == 79:
    
25.             count += s[a+1][b]
    
26.             a += 1
    
27.         else:   
    
28.             count += min(s[a+1][b],s[a][b+1])
    
29.             if s[a+1][b] <= s[a][b+1]:
    
30.                 a += 1
    
31.             else:
    
32.                 b += 1
    
33.     print(count)
    
34.     return count
    
35. 
    
36. 
    
37. def go(a,b,c,count):
    
38.     q = [(a,b,c)]
    
39.     while len(q) != 0:
    
40.         (a,b,c) = q.pop(0)
    
41.         
    
42.         for i in t:
    
43.             a1 = a + i[0]
    
44.             b1 = b + i[1]
    
45.             if 0<=a1<80 and 0<=b1<80:
    
46.                 c1 = c + s[a1][b1]
    
47.                
    
48.                 if c1 <count:
    
49.                     if (a1,b1) == (79,79):
    
50.                         print(c1)
    
51.                         return c1
    
52.                     if (a1,b1) not in right:
    
53.                         
    
54.                         q.append((a1,b1,c1))
    
55.                         right[(a1,b1)] = c1
    
56.                     if (a1,b1) in right:
    
57.                         if c1 < right[a1,b1]:
    
58.                             if (a1,b1,right[(a1,b1)]) in q:
    
59.                                 q.remove((a1,b1,right[(a1,b1)]))
    
60.                            
    
61.                             right[(a1,b1)] = c1
    
62.                             right1[(a1,b1)] = (a,b)
    
63.                             q.append((a1,b1,c1))
    
64.                         
    
65.    
    
66.                     
    
67. def main():
    
68.     global right
    
69.     global right1
    
70.     count = move()
    
71.    
    
72.     while True:
    
73.         a = 0
    
74.         b = 0
    
75.         c = s[0][0]
    
76.         right = {(0,0):s[0][0]}
    
77.         right1 = {}
    
78.         t = go(a,b,c,count)
    
79.         if t != None:
    
80.             count = t
    
81. 
    
82.         else:
    
83.             print(count)
    
84.                
    
85.             break
    
86. 
    
87. main()
    

复制代码

guosl

参照上题。

1. /*
   
2. 答案：425185
   
3. 耗时：0.002039秒
   
4. */
   
5. #include <cstdio>
   
6. #include <algorithm>
   
7. #include <queue>
   
8. #include <omp.h>
   
9. using namespace std;
   
10. 
    
11. //四个方向
    
12. const int nDR[] = { 1,0,-1,0 };
    
13. const int nDC[] = { 0,1,0,-1 };
    
14. 
    
15. char cVisited[80][80];
    
16. int m[80][80];
    
17. 
    
18. struct stNode
    
19. {
    
20.   int r, c;
    
21.   int nSum;
    
22.   bool operator<(const stNode &n) const
    
23.   {
    
24.     return (nSum > n.nSum);
    
25.   }
    
26. };
    
27. 
    
28. int main(void)
    
29. {
    
30.   double t = omp_get_wtime();
    
31.   FILE *fin = NULL;
    
32.   freopen_s(&fin, "p083_matrix.txt", "r", stdin);//打开文件
    
33.   //读入数据
    
34.   for (int i = 0; i < 80; ++i)
    
35.   {
    
36.     for (int j = 0; j < 79; ++j)
    
37.       scanf_s("%d,", &(m[i][j]));
    
38.     scanf_s("%d", &(m[i][79]));
    
39.   }
    
40.   fclose(fin);
    
41.   int nMinSum = 0x7fffffff;
    
42.   char cVisited[80][80];//访问过的标志
    
43.   priority_queue<stNode> q;//优先队列
    
44.   //初始化数据
    
45.   memset(cVisited, 0, sizeof(cVisited));
    
46.   stNode nTemp;
    
47.   nTemp.r = 0;
    
48.   nTemp.c = 0;
    
49.   nTemp.nSum = m[0][0];
    
50.   cVisited[0][0] = 1;
    
51.   q.push(nTemp);
    
52.   while (!q.empty())//广搜
    
53.   {
    
54.     stNode nTop = q.top();//取出和最小的点
    
55.     q.pop();
    
56.     if (nTop.r == 79 && nTop.c == 79)//如果以到终点
    
57.     {
    
58.       nMinSum = min(nMinSum, nTop.nSum);
    
59.       break;
    
60.     }
    
61.     for (int i = 0; i < 4; ++i)//从当前点向周围四个方向探索
    
62.     {
    
63.       int nr = nTop.r + nDR[i];
    
64.       int nc = nTop.c + nDC[i];
    
65.       if (nr >= 0 && nr < 80 && nc >= 0 && nc < 80 && cVisited[nr][nc] == 0)//检查新探索的点是否合法或尚未访问过
    
66.       {
    
67.         cVisited[nr][nc] = 1;
    
68.         nTemp.r = nr;
    
69.         nTemp.c = nc;
    
70.         nTemp.nSum = nTop.nSum + m[nr][nc];
    
71.         q.push(nTemp);
    
72.       }
    
73.     }
    
74.   }
    
75.   t = omp_get_wtime() - t;
    
76.   printf_s("%d\n%lf\n", nMinSum, t);
    
77.   return 0;
    
78. }

复制代码