Pagini recente » Cod sursa (job #2295949) | Cod sursa (job #2299252) | Cod sursa (job #51037) | Cod sursa (job #2342756) | Cod sursa (job #672429)
Cod sursa(job #672429)
#include<iostream>
#include<fstream>
using namespace std;
int dist_min(int x,int y,int dist,short **cost)
{
/*1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from source to v
4 previous[v] := undefined ; // Previous node in optimal path from source
5 end for ;
6 dist[source] := 0 ; // Distance from source to source
7 Q := the set of all nodes in Graph ; // All nodes in the graph are unoptimized - thus are in Q
8 while Q is not empty: // The main loop
9 u := vertex in Q with smallest distance in dist[] ;
10 if dist[u] = infinity:
11 break ; // all remaining vertices are inaccessible from source
12 end if ;
13 remove u from Q ;
14 for each neighbor v of u: // where v has not yet been removed from Q.
15 alt := dist[u] + dist_between(u, v) ;
16 if alt < dist[v]: // Relax (u,v,a)
17 dist[v] := alt ;
18 previous[v] := u ;
19 decrease-key v in Q; // Reorder v in the Queue
20 end if ;
21 end for ;
22 end while ;
23 return dist[] ;
24 end Dijkstra.
if(cost[x][y] == -2) {
return dist;
}
*/
return 0;
}
int main()
{
char linie[256];
ifstream f("RJ.in");
ofstream g("RJ.out");
int n,m,i,j;
f>>n;
f>>m;
f.getline(linie,256);
short** cost;
char mat[n+2][m+2];
int RomeoX,RomeoY;
cost = new short*[n+2];
for(i=0;i<n+2;i++)
cost[i] = new short[m+2];
for(i=1;i<n+1;i++)
{
for(j=1;j<m+1;j++)
{
mat[i][j]=f.get();
switch(mat[i][j])
{
case 'X':
cost[i][j]=-1;
break;
case ' ':
cost[i][j]=10000;
break;
case 'R':
cost[i][j]=0;
RomeoX=i;
RomeoY=j;
break;
case 'J':
cost[i][j]=-2;
break;
}
}
f.getline(linie,256);
}
for(i=0;i<n+2;i++)
{
cost[i][0]=-1;
cost[i][n+1]=-1;
}
for(i=0;i<m+2;i++)
{
cost[0][i]=-1;
cost[m+1][i]=-1;
}
int dist=dist_min(RomeoX,RomeoY,0,cost);
if(dist%2==0)
{
g<<dist/2;
}
else g<<dist/2+1;
f.close();
g.close();
return 0;
}