DIJKSTRA  IN 2 D  MATRIX  USING  PRIORITY QUEUE :)

SPOJ SHOPPING


#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
int indx[]={-1,0,0,+1};
int indy[]={0,+1,-1,0};
int w,h;
string a[1000];

#define pp pair<int,pair<int,int> >

class Prioritize
{
public:
    int operator() ( const pair<int,pair<int,int> >& p1, const pair<int,pair<int,int> >& p2 )
    {
        return p1.first > p2.first;
    }
};

void dij(int x,int y,int x1,int y1)
{
  //cout<<"gaya"<<endl;
 int visited[h][w];
 int i,j,dt1,dt2,dt3;

 for(i=0;i<h;i++)
   for(j=0;j<w;j++)
     visited[i][j]=0;

 int dist[h][w];
 for(i=0;i<h;i++)
   for(j=0;j<w;j++)
     dist[i][j]=INT_MAX;

  visited[x][y]=1;
  dist[x][y]=0;

  priority_queue<pp, vector<pp > , Prioritize > Q;

  pair<int,pair<int,int> > temp;
  temp.f=0; temp.s.f=x; temp.s.s=y;

  Q.push(temp);
  while(!Q.empty())
  {
    temp=Q.top();
    Q.pop();
     //cout<<temp.f<<" "<<temp.s.f<<" "<<temp.s.s<<endl;
     for(i=0;i<4;i++)
     {
      if(temp.s.f+indx[i]>=0 && temp.s.f+indx[i]<h && temp.s.s+indy[i]>=0 && temp.s.s+indy[i]<w)
      if(visited[temp.s.f+indx[i]][temp.s.s+indy[i]]==0 && a[temp.s.f+indx[i]][temp.s.s+indy[i]]!='X')
      if(dist[temp.s.f+indx[i]][temp.s.s+indy[i]] > temp.f+a[temp.s.f+indx[i]][temp.s.s+indy[i]]-48)
       {
       // cout<<temp.f<<"+"<<a[temp.s.f+indx[i]][temp.s.s+indy[i]]-48<<endl;
        dist[temp.s.f+indx[i]][temp.s.s+indy[i]]=temp.f+a[temp.s.f+indx[i]][temp.s.s+indy[i]]-48;
        dt1=dist[temp.s.f+indx[i]][temp.s.s+indy[i]];
        dt2=temp.s.f+indx[i];
        dt3=temp.s.s+indy[i];
        visited[temp.s.f+indx[i]][temp.s.s+indy[i]]=1;
        Q.push(make_pair(dt1,make_pair(dt2,dt3)));

       }
     }
    }

   /* for(i=0;i<h;i++){
     for(j=0;j<w;j++)
      cout<<dist[i][j]<<" ";
        cout<<endl;}*/

    int mini=INT_MAX;
    for(i=0;i<4;i++)
     {
      if(x1+indx[i]>=0 && x1+indx[i]<h && y1+indy[i]>=0 && y1+indy[i]<w)
        if(dist[x1+indx[i]][y1+indy[i]]<mini)
         mini=dist[x1+indx[i]][y1+indy[i]];
     }
   cout<<mini<<endl;
  }


int main()
{
 while(1)
 {

 cin>>w>>h;
 int i,j,x2,y2,x,y;

 if(w==0 && h==0)
  break;

 for(i=0;i<h;i++)
  cin>>a[i];

 for(i=0;i<h;i++)
 for(j=0;j<w;j++)
 {
  if(a[i][j]=='S')
   {x=i; y=j;}
  if(a[i][j]=='D')
  { x2=i;y2=j;}
 }
 a[x2][y2]='X';
dij(x,y,x2,y2);
}
return 0;
}