Artifact Content
Not logged in

Artifact 067a5c147f5030d59faa8d50b3c7f425f899e8f7


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

vector< vector<LL> > mMul( const vector< vector<LL> >& A, const vector< vector<LL> >& B )
{
	const int n = A.size();

	vector< vector<LL> > C(n, vector<LL>(n));
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j) {
			LL Cij = 0;
			for(int k=0; k<n; ++k)
				Cij += A[i][k] * B[k][j];
			C[i][j] = Cij % 1000003;
		}
	return C;
}

vector< vector<LL> > mPow( vector< vector<LL> > M, int t ) // t>0
{
	vector< vector<LL> > R;
	for(; t; t>>=1, M=mMul(M,M))
		if( t&1 )
			R = (R.empty() ? M : mMul(R,M));
	return R;
}

class DrivingAround
{
public:
	int numberOfWays(vector <string> adj, int start, int finish, int time) 
	{
		int n = adj.size()*5;
		vector< vector<LL> > M(n, vector<LL>(n));
		for(int u=0; u<adj.size(); ++u)
			for(int d=0; d<4; ++d)
				M[u*5+d+1][u*5+d] = 1;

		for(int u=0; u<adj.size(); ++u)
		for(int v=0; v<adj.size(); ++v)
			if( adj[u][v] != '.' )
				M[u*5][v*5+adj[u][v]-'0'-1] = 1;

		return int( mPow(M, time)[start*5][finish*5] );
	}

// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
	private:
	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(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arr0[] = {".12",
 "2.1",
 "12."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 2; int Arg3 = 5; int Arg4 = 8; verify_case(0, Arg4, numberOfWays(Arg0, Arg1, Arg2, Arg3)); }
	void test_case_1() { string Arr0[] = {"....52....",
 "..5.......",
 "..........",
 ".......1..",
 "......42.2",
 "5...4.....",
 ".5...4...1",
 "......5...",
 ".3244.....",
 ".........."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 2; int Arg2 = 2; int Arg3 = 10; int Arg4 = 0; verify_case(1, Arg4, numberOfWays(Arg0, Arg1, Arg2, Arg3)); }
	void test_case_2() { string Arr0[] = {"...14....1",
 "......13..",
 ".2...4....",
 "....52.5..",
 "1.3..4....",
 ".3....35.5",
 "4......1.1",
 "..4.4.1.54",
 "....4.11.5",
 "31144.2.4."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 7; int Arg2 = 2; int Arg3 = 100; int Arg4 = 316984; verify_case(2, Arg4, numberOfWays(Arg0, Arg1, Arg2, Arg3)); }
	void test_case_3() { string Arr0[] = {".555555555", "5.55555555", "55.5554555", "555.555555", "5555.55555", "55555.5555", "555555.555", "5555555.55", "55553555.5", "555555555."};
vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 7; int Arg3 = 1000000000; int Arg4 = 255218; verify_case(3, Arg4, numberOfWays(Arg0, Arg1, Arg2, Arg3)); }
// END CUT HERE
};
// BEGIN CUT HERE 
int main() { DrivingAround().run_test(-1); }
// END CUT HERE