Artifact Content
Not logged in

Artifact 345e49df172a4d838458f8a09fe07f6629b6a83c


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

static const int INF = 0x3fffffff;
LL gcd(LL x, LL y) { while(x) swap(x,y%=x); return y; }
static const int dy[] = {-1,+1,0,0};
static const int dx[] = {0,0,-1,+1};

class MeetInTheMaze { public:
	int H, W;
	map<char, int> count;

	void setup_maze(vector<string>& maze)
	{
		setup_sentinel(maze);

		H = maze.size();
		W = maze[0].size();

		for(int y=0; y<H; ++y)
		for(int x=0; x<W; ++x)
			count[maze[y][x]] ++;
	}

	void setup_sentinel(vector<string>& maze)
	{
		for(int y=0; y<maze.size(); ++y)
			maze[y] = '#' + maze[y] + '#';
		maze.insert( maze.begin(), string(maze[0].size(), '#') );
		maze.insert( maze.end(),   string(maze[0].size(), '#') );
	}

	string ratio2str(LL si, LL bo)
	{
		if( si >= INF )
			return "";
		LL g = gcd(si, bo);
		stringstream ss;
		ss << si/g << "/" << bo/g;
		return ss.str();
	}

	LL dijkstra(const vector< vector<int> >& FD, const vector< vector<int> >& RD, const vector<string>& maze)
	{
		typedef pair<int,int>   vert;
		typedef LL              cost;
		typedef pair<cost,vert> cvert;

		vector<bool> V(H*W);
		priority_queue< cvert, vector<cvert>, greater<cvert> > Q;
		for(int y=0; y<H; ++y)
		for(int x=0; x<W; ++x)
			if( maze[y][x] != '#' )
				Q.push( cvert(FD[y][x]+RD[y][x], make_pair(y,x)) );

		cost total = 0;
		while( !Q.empty() )
		{
			cvert v = Q.top(); Q.pop();
			cost c = v.first;
			int y = v.second.first;
			int x = v.second.second;
			if( V[y*W+x] )
				continue;
			V[y*W+x] = true;

			if( maze[y][x] == 'L' )
				total += c;

			for(int k=0; k<4; ++k) {
				int yy = y+dy[k];
				int xx = x+dx[k];
				cvert u(c+1, make_pair(yy,xx));
				if( maze[yy][xx]!='#' && !V[yy*W+xx] )
					Q.push(u);
			}
		}
		return total;
	}

	void bfs(vector< vector<int> >& D, vector<string>& m, int y, int x)
	{
		vector< pair<int,int> > Q(1, make_pair(y,x));
		D[y][x] = 0;
		for(int s=1; !Q.empty(); ++s)
		{
			vector< pair<int,int> > Q2;
			for(int i=0; i<Q.size(); ++i){
				y = Q[i].first;
				x = Q[i].second;
				for(int k=0; k<4; ++k) {
					int yy = y+dy[k];
					int xx = x+dx[k];
					if( m[yy][xx]!='#' && D[yy][xx]==INF )
						Q2.push_back(make_pair(yy,xx)), D[yy][xx]=s;
				}
			}
			Q.swap(Q2);
		}
	}

	string getExpected(vector <string> maze)
	{
		setup_maze(maze);

		LL total = 0;
		for(int fy=0; fy<H; ++fy)
		for(int fx=0; fx<W; ++fx)
		if( maze[fy][fx] == 'F' )
		{
			// Fill the 2d-map FD with the distance from (fy,fx) in the maze.
			vector< vector<int> > FD(H, vector<int>(W, INF));
			bfs(FD, maze, fy, fx);
			for(int ry=0; ry<H; ++ry)
			for(int rx=0; rx<W; ++rx)
			if( maze[ry][rx] == 'R' )
			{
				// Fill the 2d-map RD with the distance from (ry,rx) in the maze.
				vector< vector<int> > RD(H, vector<int>(W, INF));
				bfs(RD, maze, ry, rx);
				// Compute the distances of all the cells from the base "FD+RD"
				total += dijkstra(FD, RD, maze);
			}
		}
		return ratio2str(total, count['F']*count['R']*count['L']);
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const string& Expected, const string& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, MeetInTheMaze().getExpected(maze));}
int main(){

CASE(0)
	string maze_[] = { "#########", 
  "####F####", 
  "##L...R##", 
  "####L####", 
  "#########" }
;
	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
	string _ = "9/2"; 
END
CASE(1)
	string maze_[] = { "LR", 
  "RF" }
;
	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
	string _ = "2/1"; 
END
CASE(2)
	string maze_[] = { "..F.#...", 
  "L.F.#..L", 
  "..F.#...", 
  ".R.#..L.", 
  "...#....", 
  "..R#.L.." }
;
	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
	string _ = ""; 
END
CASE(3)
	string maze_[] = { ".L..L..L..", 
  "..........", 
  "..........", 
  "..........", 
  "........R.", 
  "...R......", 
  "..........", 
  "..........", 
  "..........", 
  ".......F.." }
;
	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
	string _ = "40/3"; 
END
CASE(4)
	string maze_[] = { "#.#....#...#.#", 
  "#...#..#......", 
  ".L#...#R#..#F.", 
  "#...#......#..", 
  "#......#.....#", 
  ".R.....F....L.", 
  "##..#.......#.", 
  "#........##...", 
  ".F...##L#..#R#" }
;
	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
	string _ = "362/27"; 
END
CASE(5)
	string maze_[] = { "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLFLLLLLLLLLFLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLFFLLLLLLLLLLRLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLFLLLLLLLLLLLLLLF", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLF", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLFLLL", 
  "LLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLR", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLFFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "FLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLFLLLLLLLLLRLLLLLLLLLLLLLLLLLLLRLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLFLLLLLLLLLLLLLLLLRLLLLLLLLLRLLLLLLLLLLLLRLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "FLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
  "LLLLLLLLLLLLLLLLLLLLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLL" }
;
	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
	string _ = "210623/4100"; 
END
/*
CASE(6)
	string maze_[] = ;
	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
	string _ = ; 
END
CASE(7)
	string maze_[] = ;
	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
	string _ = ; 
END
*/
}
// END CUT HERE