Click here to Skip to main content
15,900,907 members
Please Sign up or sign in to vote.
2.50/5 (2 votes)
See more:
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


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#
Delphi
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.
Posted
Updated 20-Jun-14 22:51pm
v3
Comments
OriginalGriff 21-Jun-14 4:42am    
And?
What have you tried?
Where are you stuck?
What help do you need?
[no name] 21-Jun-14 4:55am    
i have tried)
phil.o 21-Jun-14 8:13am    
"What have you tried?
- I have tried."
How funny!

1 solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900