UVA 929  Number Maze Dijkstra based problem. We have already discussed Dijkstra algorithm for shortest path from source to destination here http://wikistack.com/shortest-path-problem-dijkstras-algorithm/. The given problem at this link https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=870 is based on Dijkstra’ algorithm. Let us practice it for applying Dijkstra algorithm.

UVA 929 Number Maze Dijkstra based problem

Your are give a maze filled with some numbers from 0 to 9, find the min cost to reach from top left corner to bottom right corner. The maze can be traversed following any orthogonal direction (i.e.,north, south, east and west).

#include<iostream>
#include<climits>
#include<cstring>
#include<cstdio>
using namespace std;

#define INF 1000000000
#define N 1000
#define M 1000

int g[N][M];
int dist[N][M];
int visited[N][M];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

bool isSafe(int x, int y, int row, int col)
{
  if (x >= 0 && x < row && y >= 0 && y < col
   && dist[x][y] != 0 && !visited[x][y])
   return true;
   
   return false;
}

void minindex (int &x, int &y, int row, int col)
{
  int min = INF;
  for (int i = 0; i < row; i++)
    {
      for (int j = 0; j < col; j++)
	{
	  if (dist[i][j] < min && !visited[i][j])
	    {
	      min = dist[i][j];
	      x = i;
	      y = j;
	    }
	}
    }
}

void dijk (int u, int v, int &ans, int row, int col)
{
  dist[u][v] = 0;

  for (int i = 0; i < row; i++)
    {
      for (int j = 0; j < col; j++)
	{
	  int x;
	  int y;
	  minindex (x, y, row, col);
	  visited[x][y] = 1;
	  for (int ii = 0; ii < 4; ii++)
	    {
	      int xx = x + dx[ii];
	      int yy = y + dy[ii];
	      if (isSafe(xx,yy,row,col))
		{
		  if (dist[xx][yy] > dist[x][y] + g[xx][yy])
		    {
		      dist[xx][yy] = dist[x][y] + g[xx][yy];
		    }
		}
	    }

	}
    }
  ans = dist[row - 1][col - 1];
}

int
main ()
{
  freopen ("929.txt", "r", stdin);
  int t = 0;
  cin >> t;
  for (int test = 0; test < t; test++)
    {
      int row = 0;
      int col = 0;
      int ans = 0;
      cin >> row >> col;
       for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                dist[i][j] = INF;
                visited[i][j] = false;
                g[i][j] = 0;
            }
        }
      for (int i = 0; i < row; i++)
	{
	  for (int j = 0; j < col; j++)
	    {
	      cin >> g[i][j];
	    }
	}

      dijk (0, 0, ans, row, col);
      cout << ans << endl;
      ans = 0;
    }	// test end
  return 0;
}


Related Contents to follow