如何在二维数组中找到最短路径 [英] How find shortest path in 2d Array

问题描述

我有二维数组.我想找到从左上值到右下的最短路径.我想使用Deikstra algho，但是要占用很多内存.

I have 2d array. I want find shortest path from left top value to right down. I want use Deikstra algho, but it take much memory.

0 2 2 2 2 2 
1 0 1 0 0 1
2 2 2 0 2 2 
2 2 2 0 1 0

那就是我想要找到的路径.有人有C#代码吗?
0 2 2 2 2 2
1 0 1 0 0 1
2 2 2 0 2 2
2 2 2 0 1 0

我用pascal制作，但不能用c#
制作

Thats is path i want found. Does anybode have c# code?
0 2 2 2 2 2
1 0 1 0 0 1
2 2 2 0 2 2
2 2 2 0 1 0

i make it in pascal, but cannot make in c#

const maxn = 40;
var n, m : integer;
    a : array [1..maxn, 1..maxn] of integer;
    dist : array [1..maxn * maxn] of integer;
    bool : array [1..maxn * maxn] of boolean;

procedure readData;
var i, j : integer;
begin
  read (n, m);
  for i := 1 to n do
    for j := 1 to m do
      read (a[i, j]);
end;

function num (x, y : integer) : integer;
begin
  num := (x  - 1) * m + y;
end;

procedure solve;
var i, cur, min : integer;
    x, y : integer;
begin
  fillchar (bool, sizeof (bool), false);
  fillchar (dist, sizeof (dist), $FF);
  bool[1] := true;
  dist[1] := a[1, 1];
  cur := 1;

  while cur <> n * m do
  begin
    x := cur div m + 1;
    y := cur mod m;
    if cur mod m = 0 then
    begin
      x := x - 1;
      y := m;
    end;

    if (y > 1) and ((dist[num (x, y - 1)] = -1) or (dist[num (x, y - 1)] > dist[num (x, y)] + a[x, y - 1])) then
      dist[num (x, y - 1)] := dist[num (x, y)] + a[x, y - 1];
    if (y < m) and ((dist[num (x, y + 1)] = -1) or (dist[num (x, y + 1)] > dist[num (x, y)] + a[x, y + 1])) then
      dist[num (x, y + 1)] := dist[num (x, y)] + a[x, y + 1];
    if (x > 1) and ((dist[num (x - 1, y)] = -1) or (dist[num (x - 1, y)] > dist[num (x, y)] + a[x - 1, y])) then
      dist[num (x - 1, y)] := dist[num (x, y)] + a[x - 1, y];
    if (x < n) and ((dist[num (x + 1, y)] = -1) or (dist[num (x + 1, y)] > dist[num (x, y)] + a[x + 1, y])) then
      dist[num (x + 1, y)] := dist[num (x, y)] + a[x + 1, y];
    min := 10000;
    for i := 1 to n * m do
      if (not ((dist[i] = -1) or (bool[i]))) and (dist[i] < min) then
      begin
        min := dist[i];
        cur := i;
      end;
    bool[cur] := true;
  end;
  writeln (dist[n * m]);
end;

begin
  assign (input, 'input.txt'); reset (input);
  assign (output, 'output.txt'); rewrite (output);
  readData;
  solve;
  close (input);
  close (output);
end.

推荐答案

FF)； bool [ 1 ]:= true; dist [ 1 ]:= a [ 1 ， 1 ]; cur:= 1 ; while cur<> n * m 做 开始 x:= cur div m + 1 ; y:= cur mod m; 如果 cur mod m = 0 然后 开始 x:= x- 1 ; y:= m; 结束； 如果(y> 1) and ((dist [num(x，y-1)] = -1)或(dist [num(x，y-1)]> dist [num(x，y)] + a [x，y- 1 ]] ))然后 dist [num(x，y-1)]:= dist [num(x，y)] + a [x，y- 1 ]; 如果(y< m) and ((dist [num(x，y + 1)] = -1)或(dist [num(x，y + 1)]> dist [num(x，y)] + a [x，y + 1 ]] ))然后 dist [num(x，y + 1)]:= dist [num(x，y)] + a [x，y + 1 ]; 如果(x> 1) and ((dist [num(x- 1 ，y)]> dist [num( x，y)] + a [x- 1 ，y]))然后 dist [num(x- 1 ，y)]:= dist [num(x，y)] + a [x- 1 ，y]; 如果(x< n) and ((dist [num(x + 1 ，y)]> dist [num( x，y)] + a [x + 1 ，y]))然后 dist [num(x + 1 ，y)]:= dist [num(x，y)] + a [x + 1 ，y]; 最小:= 10000 ; for i:= 1 to n * m 做 如果(不是((dist [i] = -1)或(bool [i]))))和(dist [i]< min)然后 开始 min:= dist [i]; cur:=我; 结束； bool [cur]:= true; 结束； writeln(dist [n * m]); 结束； 开始 分配(input，' input.txt')；重置(输入)； 分配(输出，' output.txt');重写(输出)； readData; 解决; 关闭(输入)； 关闭(输出)； 结束.

FF); bool[1] := true; dist[1] := a[1, 1]; cur := 1; while cur <> n * m do begin x := cur div m + 1; y := cur mod m; if cur mod m = 0 then begin x := x - 1; y := m; end; if (y > 1) and ((dist[num (x, y - 1)] = -1) or (dist[num (x, y - 1)] > dist[num (x, y)] + a[x, y - 1])) then dist[num (x, y - 1)] := dist[num (x, y)] + a[x, y - 1]; if (y < m) and ((dist[num (x, y + 1)] = -1) or (dist[num (x, y + 1)] > dist[num (x, y)] + a[x, y + 1])) then dist[num (x, y + 1)] := dist[num (x, y)] + a[x, y + 1]; if (x > 1) and ((dist[num (x - 1, y)] = -1) or (dist[num (x - 1, y)] > dist[num (x, y)] + a[x - 1, y])) then dist[num (x - 1, y)] := dist[num (x, y)] + a[x - 1, y]; if (x < n) and ((dist[num (x + 1, y)] = -1) or (dist[num (x + 1, y)] > dist[num (x, y)] + a[x + 1, y])) then dist[num (x + 1, y)] := dist[num (x, y)] + a[x + 1, y]; min := 10000; for i := 1 to n * m do if (not ((dist[i] = -1) or (bool[i]))) and (dist[i] < min) then begin min := dist[i]; cur := i; end; bool[cur] := true; end; writeln (dist[n * m]); end; begin assign (input, 'input.txt'); reset (input); assign (output, 'output.txt'); rewrite (output); readData; solve; close (input); close (output); end.

请参阅以下链接:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm [ http: //www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527/AStar-A-Implementation-in-C-Path-Finding-PathFinder.htm [

refer below links:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm[^]
and
http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527/AStar-A-Implementation-in-C-Path-Finding-PathFinder.htm[^]

这篇关于如何在二维数组中找到最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！