题目83：允许向上下左右移动的情况下从左上角到右下角的最小路径和是多少？
本帖最后由 欧拉计划 于 2016-8-9 17:39 编辑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。路径用红色标出。
包含一个 80×80 的矩阵，在允许向上，下，左，右移动的情况下，找出从左上角到右下角的最小路径和。 a=[for j in range(85)]
dp=[for j in range(85)]
vis=[for j in range(85)]
tot=0
way=[]
Mini=-1
Minj=-1
Min=9999999999
dx=
dy=
def find():
global Mini
global Minj
global Min
Mini=-1
Minj=-1
Min=9999999999
for w in range(len(way)):
i=way
j=way
for k in range(4):
nx=i+dx
ny=j+dy
if nx>=0 and nx<80 and ny>=0 and ny<80 and vis==0 and dp+a<Min:
Min=dp+a
Mini=nx
Minj=ny
def update():
global tot
global Min
x=Mini
y=Minj
dp=Min
vis=1
way.append()
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=s.split(',')
for i in range(80):
for j in range(80):
a=int(a)
vis=1
dp=a
tot+=1
way.append()
while tot<6400:
find() #找到最小的位置
if update()==True: #更新
break
print('bingo: ',dp)
bingo:425185 思路和上述方法一致，但是简化了算法，时间缩短了10倍{:5_95:}
#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=s.split(',')
for i in range(80):
for j in range(80):
matrix=int(matrix)
visited = [*80 for i in range(80)]
dp = [*80 for i in range(80)]
move = [(1,0),(-1,0),(0,1),(0,-1)]
checklist = [(0,0)]
dp = 4445
#define the method for searching the best way:
def findway(x,y):
if not visited:
visited = True
for m in move:
nx,ny = x+m,y+m
if 0<=nx<80 and 0<=ny<80:
dp = min(dp+matrix,dp)
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,checklist)
if len([(j,k) for j in range(80) for k in range(80) if not visited]) == 0:
visited = [*80 for i in range(80)]
checklist = [(0,0)]
if min7979 > dp:
min7979 = dp
else:
print (min7979)
break
425185
用的matlab
结果是：
ans =
425185
时间已过 0.433833 秒。
路径用matlab可以动态画出来
可惜不能上传图片 import shuzimigong as sh
t = sh.t.split('\n')
s = [[] for i in range(80)]
for i in range(80):
for each int.split(','):
s.append(int(each))
right = {(0,0):s}
right1 = {}
t = [(-1,0),(1,0),(0,1),(0,-1)]
def move():
count = s
a = 0
b = 0
while True:
if a == 79 and b == 79:
break
if a == 79 and b != 79:
count += s
b += 1
elif a != 79 and b == 79:
count += s
a += 1
else:
count += min(s,s)
if s <= s:
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
b1 = b + i
if 0<=a1<80 and 0<=b1<80:
c1 = c + s
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:
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
right = {(0,0):s}
right1 = {}
t = go(a,b,c,count)
if t != None:
count = t
else:
print(count)
break
main()
参照上题。
/*
答案：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;
int m;
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));
scanf_s("%d", &(m));
}
fclose(fin);
int nMinSum = 0x7fffffff;
char cVisited;//访问过的标志
priority_queue<stNode> q;//优先队列
//初始化数据
memset(cVisited, 0, sizeof(cVisited));
stNode nTemp;
nTemp.r = 0;
nTemp.c = 0;
nTemp.nSum = m;
cVisited = 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;
int nc = nTop.c + nDC;
if (nr >= 0 && nr < 80 && nc >= 0 && nc < 80 && cVisited == 0)//检查新探索的点是否合法或尚未访问过
{
cVisited = 1;
nTemp.r = nr;
nTemp.c = nc;
nTemp.nSum = nTop.nSum + m;
q.push(nTemp);
}
}
}
t = omp_get_wtime() - t;
printf_s("%d\n%lf\n", nMinSum, t);
return 0;
}
页:
[1]