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;
}
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;
}
sir _/\_
ReplyDelete