Artifact 3dfb717e5a03a7d868faec4583cdf3e791f1e9ba
#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 dy[] = {-1,+1,0,0};
static const int dx[] = {0,0,-1,+1};
class MazeWandering {
public:
double expectedTime(vector <string> maze)
{
int Y = maze.size();
int X = maze[0].size();
vector< vector<int> > d(Y, vector<int>(X, -1));
vector< pair<int,int> > q, Q;
for(int y=0; y<Y; ++y)
for(int x=0; x<X; ++x)
if( maze[y][x] == '*' ) {
d[y][x] = 0;
q.push_back( make_pair(y,x) );
Q.push_back( make_pair(y,x) );
}
for(int step=1; !q.empty(); ++step)
{
vector< pair<int,int> > q2;
for(int j=0; j<q.size(); ++j)
{
int qy = q[j].first;
int qx = q[j].second;
for(int i=0; i<4; ++i)
{
int y = qy+dy[i], x = qx+dx[i];
if( 0<=y && y<Y && 0<=x && x<X && maze[y][x]=='.' && d[y][x]==-1 )
{
d[y][x] = step;
q2.push_back( make_pair(y,x) );
Q.push_back( make_pair(y,x) );
}
}
}
q2.swap(q);
}
vector< vector<int> > w(Y, vector<int>(X, 0));
for(int j=Q.size()-1; j>0; --j)
{
int qy = Q[j].first;
int qx = Q[j].second;
for(int i=0; i<4; ++i)
{
int y = qy+dy[i], x = qx+dx[i];
if( 0<=y && y<Y && 0<=x && x<X && maze[y][x]!='X' && d[y][x] > d[qy][qx] )
w[qy][qx] += w[y][x] + 1;
}
}
double esum = 0.0;
vector< vector<double> > e(Y, vector<double>(X, 0.0));
for(int j=0; j<Q.size(); ++j)
{
int qy = Q[j].first;
int qx = Q[j].second;
if( d[qy][qx] > 0 )
{
for(int i=0; i<4; ++i)
{
int y = qy+dy[i], x = qx+dx[i];
if( 0<=y && y<Y && 0<=x && x<X && maze[y][x]!='X' && d[y][x] < d[qy][qx] )
{
e[qy][qx] = e[y][x] + 1 + 2*w[qy][qx];
esum += e[qy][qx];
break;
}
}
}
}
return esum / Q.size();
}
};
// 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> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const double &Expected, const double &Received) { double diff = Expected - Received; if (diff < 0) diff = -diff; if (diff < 1e-9) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}
template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
string maze_[] = {"*",
"."};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
double RetVal = 0.5;
return verify_case(RetVal, MazeWandering().expectedTime(maze)); }
int Test_(Case_<1>) {
string maze_[] = {"*.."};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
double RetVal = 2.3333333333333335;
return verify_case(RetVal, MazeWandering().expectedTime(maze)); }
int Test_(Case_<2>) {
string maze_[] = {"...",
"X*X",
"..."};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
double RetVal = 4.857142857142857;
return verify_case(RetVal, MazeWandering().expectedTime(maze)); }
int Test_(Case_<3>) {
string maze_[] = {".*.",
".XX",
"..."};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
double RetVal = 13.714285714285714;
return verify_case(RetVal, MazeWandering().expectedTime(maze)); }
int Test_(Case_<4>) {
string maze_[] = {"*........",
"XXX.XXXX.",
".XX.X....",
".....XX.X"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
double RetVal = 167.2608695652174;
return verify_case(RetVal, MazeWandering().expectedTime(maze)); }
int Test_(Case_<5>) {
string maze_[] = {"X*X"};
vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_));
double RetVal = 0;
return verify_case(RetVal, MazeWandering().expectedTime(maze)); }
template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<> void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE