题目82：找出从左边列到右边列的最小路径和

欧拉计划

Path sum: three ways

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

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

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 left column to the right column.

题目：

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

在下面这个 5×5 的矩阵中，从最左边一列的任意元素开始，到最右边一列的任意元素结束，最短的路径和是 994，其中允许移动的方向为上，下和右。路径用红色标出。

p082_matrix.txt (30.57 KB, 下载次数: 10)

2016-8-9 16:53 上传

点击文件名下载附件

包含一个 80×80 的矩阵，找出从最左边一列到最右边一列的最小路径和。

jerryxjr1220

260324
[Finished in 0.1s]

ls = [.......]

ans=[ls[i][79] for i in range(80)]  
  
for i in range(78,-1,-1):  
    ans[0]=ans[0]+ls[0][i]  
  
#向下  
    for j in range(1,80):  
        ans[j]=min(ans[j]+ls[j][i],ans[j-1]+ls[j][i])  
  
#向上  
    for j in range(78,-1,-1):  
        ans[j]=min(ans[j],ans[j+1]+ls[j][i])  
  
print(min(ans))  

najin

用的matlab
结果是
     260324

时间已过 0.012373 秒。
>>

fc1735

f = open('82.txt', 'r')
mat = list(map(lambda x: list(map(int, x.split(','))),
            filter(lambda x: len(x) != 0, f.read().split('\n'))))

for j in range(1, len(mat[0])):
  for i in range(len(mat) - 1):
    mat[i+1][j-1] = min(mat[i+1][j-1], mat[i][j-1] + mat[i][j])
  for i in range(len(mat) - 1, 0, -1):
    mat[i-1][j-1] = min(mat[i-1][j-1], mat[i][j-1] + mat[i][j])
  for i in range(len(mat)):
    mat[i][j] += mat[i][j-1]

print(min(map(lambda x: x[-1], mat)))

https://github.com/devinizz/project_euler/blob/master/page02/82.py

guosl

典型的光度搜索。

/*
答案：260324
耗时：0.023621秒（单核）
      0.005743秒（六核）
*/
#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, "p082_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;
#pragma omp parallel for shared(m) reduction(min:nMinSum)
  for (int r = 0; r < 80; ++r)//对第一列进行循环
  {
    char cVisited[80][80];//访问过的标志
    priority_queue<stNode> q;//优先队列
    //初始化数据
    memset(cVisited, 0, sizeof(cVisited));
    stNode nTemp;
    nTemp.r = r;
    nTemp.c = 0;
    nTemp.nSum = m[r][0];
    cVisited[r][0] = 1;
    q.push(nTemp);
    while (!q.empty())//广搜
    {
      stNode nTop = q.top();//取出和最小的点
      q.pop();
      if (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;
}