题目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, 下载次数: 17)

2016-8-9 17:09 上传

点击文件名下载附件

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

jerryxjr1220

a=[[0 for i in range(85)]for j in range(85)]
dp=[[999999999 for i in range(85)]for j in range(85)]
vis=[[0 for i in range(85)]for j in range(85)]
tot=0
way=[]
Mini=-1
Minj=-1
Min=9999999999
dx=[1,-1,0,0]
dy=[0,0,1,-1]

def find():
    global Mini
    global Minj
    global Min
    Mini=-1
    Minj=-1
    Min=9999999999
    for w in range(len(way)):
        i=way[w][0]
        j=way[w][1]
        for k in range(4):
            nx=i+dx[k]
            ny=j+dy[k]
            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:
                Min=dp[i][j]+a[nx][ny]
                Mini=nx
                Minj=ny

def update():
    global tot
    global Min
    x=Mini
    y=Minj
    dp[x][y]=Min
    vis[x][y]=1
    way.append([x,y])
    tot+=1
    print('第',tot,'个节点确定：(',x,',',y,')')
    if x==79 and y==79:
        return True
    else:
        return False

file=open('matrix.txt')
f=file.read()
file.close()
s=f.split('\n')
for i in range(80):
    a[i]=s[i].split(',')
for i in range(80):
    for j in range(80):
        a[i][j]=int(a[i][j])
vis[0][0]=1
dp[0][0]=a[0][0]
tot+=1
way.append([0,0])
while tot<6400:
    find() #找到最小的位置
    if update()==True: #更新
        break
print('bingo: ',dp[79][79])

bingo:  425185

jerryxjr1220

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

#coding:utf-8
#initiate:
file=open('matrix.txt')
f=file.read()
file.close()
s=f.split('\n')
matrix = [[]*80 for i in range(80)]
for i in range(80):
    matrix[i]=s[i].split(',')
for i in range(80):
    for j in range(80):
        matrix[i][j]=int(matrix[i][j])

visited = [[False]*80 for i in range(80)]
dp = [[999999]*80 for i in range(80)]
move = [(1,0),(-1,0),(0,1),(0,-1)]
checklist = [(0,0)]
dp[0][0] = 4445

#define the method for searching the best way:
def findway(x,y):
        if not visited[x][y]:
                visited[x][y] = True
                for m in move:
                        nx,ny = x+m[0],y+m[1]
                        if 0<=nx<80 and 0<=ny<80:
                                dp[nx][ny] = min(dp[x][y]+matrix[nx][ny],dp[nx][ny])
                                checklist.append((nx,ny))

#min7979 is the min price to go:
min7979 = 999999

#repeat again and again until the min is stable, that's the answer.
while True:
        for i in range(len(checklist)):
                findway(checklist[i][0],checklist[i][1])
        if len([(j,k) for j in range(80) for k in range(80) if not visited[j][k]]) == 0:
                visited = [[False]*80 for i in range(80)]
                checklist = [(0,0)]
                if min7979 > dp[79][79]:
                        min7979 = dp[79][79]
                else:
                        print (min7979)
                        break

425185
[Finished in 3.8s]

najin

用的matlab
结果是：
ans =

      425185

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

JAY饭

import shuzimigong as sh

t = sh.t.split('\n')
s = [[] for i in range(80)]
for i in range(80):
    for each in  t[i].split(','):
        s[i].append(int(each)) 


right = {(0,0):s[0][0]}
right1 = {}
t = [(-1,0),(1,0),(0,1),(0,-1)]

def move():
    count = s[0][0]
    a = 0
    b = 0
    while True:
        if a == 79 and b == 79:
            break
        if a == 79 and b != 79:
            count += s[a][b+1]
            b += 1
        elif a != 79 and b == 79:
            count += s[a+1][b]
            a += 1
        else:    
            count += min(s[a+1][b],s[a][b+1]) 
            if s[a+1][b] <= s[a][b+1]:
                a += 1
            else:
                b += 1
    print(count)
    return count


def go(a,b,c,count):
    q = [(a,b,c)]
    while len(q) != 0:
        (a,b,c) = q.pop(0)
        
        for i in t:
            a1 = a + i[0]
            b1 = b + i[1]
            if 0<=a1<80 and 0<=b1<80:
                c1 = c + s[a1][b1]
                
                if c1 <count:
                    if (a1,b1) == (79,79):
                        print(c1)
                        return c1
                    if (a1,b1) not in right:
                        
                        q.append((a1,b1,c1))
                        right[(a1,b1)] = c1
                    if (a1,b1) in right:
                        if c1 < right[a1,b1]:
                            if (a1,b1,right[(a1,b1)]) in q:
                                q.remove((a1,b1,right[(a1,b1)]))
                            
                            right[(a1,b1)] = c1
                            right1[(a1,b1)] = (a,b)
                            q.append((a1,b1,c1))
                        
    
                    
def main():
    global right
    global right1
    count = move()
    
    while True:
        a = 0
        b = 0
        c = s[0][0]
        right = {(0,0):s[0][0]}
        right1 = {}
        t = go(a,b,c,count)
        if t != None:
            count = t

        else:
            print(count)
                
            break

main()

guosl

参照上题。

/*
答案：425185
耗时：0.002039秒
*/
#include <cstdio>
#include <algorithm>
#include <queue>
#include <omp.h>
using namespace std;

//四个方向
const int nDR[] = { 1,0,-1,0 };
const int nDC[] = { 0,1,0,-1 };

char cVisited[80][80];
int m[80][80];

struct stNode
{
  int r, c;
  int nSum;
  bool operator<(const stNode &n) const
  {
    return (nSum > n.nSum);
  }
};

int main(void)
{
  double t = omp_get_wtime();
  FILE *fin = NULL;
  freopen_s(&fin, "p083_matrix.txt", "r", stdin);//打开文件
  //读入数据
  for (int i = 0; i < 80; ++i)
  {
    for (int j = 0; j < 79; ++j)
      scanf_s("%d,", &(m[i][j]));
    scanf_s("%d", &(m[i][79]));
  }
  fclose(fin);
  int nMinSum = 0x7fffffff;
  char cVisited[80][80];//访问过的标志
  priority_queue<stNode> q;//优先队列
  //初始化数据
  memset(cVisited, 0, sizeof(cVisited));
  stNode nTemp;
  nTemp.r = 0;
  nTemp.c = 0;
  nTemp.nSum = m[0][0];
  cVisited[0][0] = 1;
  q.push(nTemp);
  while (!q.empty())//广搜
  {
    stNode nTop = q.top();//取出和最小的点
    q.pop();
    if (nTop.r == 79 && nTop.c == 79)//如果以到终点
    {
      nMinSum = min(nMinSum, nTop.nSum);
      break;
    }
    for (int i = 0; i < 4; ++i)//从当前点向周围四个方向探索
    {
      int nr = nTop.r + nDR[i];
      int nc = nTop.c + nDC[i];
      if (nr >= 0 && nr < 80 && nc >= 0 && nc < 80 && cVisited[nr][nc] == 0)//检查新探索的点是否合法或尚未访问过
      {
        cVisited[nr][nc] = 1;
        nTemp.r = nr;
        nTemp.c = nc;
        nTemp.nSum = nTop.nSum + m[nr][nc];
        q.push(nTemp);
      }
    }
  }
  t = omp_get_wtime() - t;
  printf_s("%d\n%lf\n", nMinSum, t);
  return 0;
}