uva: 929 – Number Maze ( Dijkstra )

 929 – Number Maze

Problem analysis:

  • find minimum cost by traversing vertexes from single source [0][0] to destination [Row-1][Col-1] .
  • given that cost or weight for each of the vertex/node in the graph.

Solution:

  • It can be solved using Single Source Shortest Path (SSSP) algorithms such as Dijkstra’s algorithm
  • Before applying Dijkstra, distance and weight data structure needs to be modified as per problem requirements
  • distance data structure is 2D array to store distance from source to each other vertex  in the row, column (r,c)  position
This C++ solution takes time: 1.715 sec

// Time: 1.715 sec
#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

#define INF 1e9

const int adjR[4] = {-1,  0, 1, 0};
const int adjC[4] = { 0, -1, 0, 1};

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector vi;

vector weight;
int row, col, r, c, i, d, newr, newc;

int dijkstra()
{
    priority_queue<iii,vector,greater> pq;
    vector<vi> dist;

    dist.clear();
    vi rowInit(col,INF);
    dist.assign(row,rowInit);

    //source dist
    dist[0][0] = weight[0][0];

    pq.push( iii( dist[0][0], ii(0,0) ) );

    while(!pq.empty())
    {
        iii u = pq.top();
        pq.pop();
        r = u.second.first;
        c = u.second.second;
        d = u.first;
        
        for(i=0;i<4;i++)
        {
            newr = r + adjR[i];
            newc= c + adjC[i];

            if(newr >= 0 && newr < row && newc >= 0 && newc < col)
            {
                if(d + weight[newr][newc] < dist[newr][newc])
                {
                     dist[newr][newc] = d + weight[newr][newc];
                     pq.push( iii(dist[newr][newc], ii(newr,newc) ) );
                }
            }
        }
    }

    return dist[row-1][col-1];
}

int main()
{
    int testcase, w;

    scanf("%d",&testcase);

    while(testcase--)
    {
        scanf("%d",&row);
        scanf("%d",&col);

        weight.clear();

        for(r=0; r<row; r++)
        {
            vi rowdata;
            for(c=0; c<col; c++)
            {
                scanf("%d",&w);
                rowdata.push_back(w);
            }
            weight.push_back(rowdata);
        }
        printf("%d\n",    dijkstra());
    }
    
    return 0;
}

 

Java solution- Time Limit Exceeded
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Vertex implements Comparable<Vertex>
{
    public int r;
    public int c;
    public int dist_frm_src;
    public Vertex(int r, int c, int d)
    {
        this.r=r;
        this.c=c;
        this.dist_frm_src=d;
    }
    @Override
    public int compareTo(Vertex other) {        
        return this.dist_frm_src - other.dist_frm_src;
    }    
}

class Main_929_Number_Maze_TimitLimitExceeded {

    static final int INFINITY = Integer.MAX_VALUE;    
    static final int[] adjR = {-1,0,1,0};
    static final int[] adjC = {0,-1,0,1};

    public static void main(String[] args) {
        

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);
        int[][] dist;
        int[][] weight;
        int row,col,i,j, new_r, new_c;
        PriorityQueue<Vertex> pq;
        Vertex u;

        int tc=sc.nextInt();
        while(tc-->0)
        {
            //input processing
            row=sc.nextInt();
            col=sc.nextInt();

            dist=new int[row+1][col+1];
            weight=new int[row+1][col+1];
            pq = new PriorityQueue<Vertex>();

            for(int r=1;r<=row;r++)                
            {
                Arrays.fill(dist[r], INFINITY);
                Arrays.fill(weight[r],INFINITY);                
            }

            for(int r=1;r<=row;r++)
                for(int c=1;c<=col;c++)
                    weight[r][c] = sc.nextInt();                    

            //Dijkstra Algorithm - SSSP
            u = new Vertex(1, 1, weight[1][1]);
            dist[1][1] = weight[1][1];                
            pq.add(u);
            while(!pq.isEmpty())
            {
                u=pq.poll();
                for(i=0;i<4;i++) //adjacent vertexes
                {
                    new_r = u.r + adjR[i];
                    new_c = u.c + adjC[i];
                    if(new_r >= 1 && new_r <= row && new_c >= 1 && new_c <= col)                    
                        if( u.dist_frm_src + weight[new_r][new_c] < dist[new_r][new_c])
                        {
                            dist[new_r][new_c] =  u.dist_frm_src + weight[new_r][new_c];
                            pq.add(new Vertex(new_r, new_c, dist[new_r][new_c]));
                        }

                }
            }
            System.out.println(dist[row][col]);
        }        
    }
}

 

Sample Input
2
4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
1
6
0 1 2 3 4 5
Sample Output
24
15

 

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: