Cod sursa(job #672429)

Utilizator CrescentselectJicol Crescent Crescentselect Data 2 februarie 2012 10:04:15
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#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;
}