kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2022 Round3 : Medium TwoMazeAlgorithms

SRM

なるほど…。
https://community.topcoder.com/stat?c=problem_statement&pm=17673&rd=19264

問題

N*Nのグリッドがある。
セルとセルの間の壁を壊し、迷路を作ることを考える。
どのセルからどのセルへも移動可能とし、かつパスが一意に定まるようにしたい。

その際、以下の2つのアルゴリズムが考えられる。

  • 左上のセルから始め、DFSする。現在いるセルから、隣接セルのうち未訪問のセルが残っている間、ランダムに一つ選んで壁を壊しそちらのセルに移動する、という手順をDFSの要領で繰り返す。
  • クラスカル法の要領で、全壁にランダムな重さを振り、各セルが連結するように軽い壁から順に壊す。

ここで、迷路が1000個与えられる。それぞれ、上記いずれかの手法で構成されている。
どちらの手法で構成されたかを99%以上当てよ。

解法

前者で構成可能な迷路は限定されるため、与えられた迷路がその条件に当てはまるかを考えよう。
各セルの連結関係を木で表現したとする。
その時、（間に壁があってもなくてもよいので）隣接するセル同士は、どちらかがどちらかの祖先でなければならない。
(DFSのアルゴリズムを考えると、そうならないケースは発生し得ない)

なので、上記関係の有無を判定しよう。

/*
int T,N,M;
string S[3030];
int A[1010][1010];

vector<int> V[2020][2020];

void dfs(int y,int x) {
	int d[4]={0,1,0,-1};
	int i;
	V[y][x].push_back(y*M+x);
	FOR(i,4) {
		int ty=y+d[i];
		int tx=x+d[i^1];
		if(S[ty][tx]=='.'&&V[ty][tx].empty()) {
			V[ty][tx]=V[y][x];
			dfs(ty,tx);
		}
	}
}

int dif(vector<int> A,vector<int> B) {
	int i;
	FOR(i,min(A.size(),B.size())) {
		if(A[i]!=B[i]) return 0;
	}
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		M=2*N+1;
		FOR(y,M) {
			cin>>S[y];
			FOR(x,M) V[y][x].clear();
		}
		dfs(1,1);
		
		int ok=1;
		FOR(y,N) FOR(x,N) {
			if(x&&dif(V[2*y+1][2*x+1],V[2*y+1][2*x+1-2])==0) ok=0;
			if(y&&dif(V[2*y+1][2*x+1],V[2*y+1-2][2*x+1])==0) ok=0;
		}
		
		if(ok) cout<<"D";
		else cout<<"M";
		
	}
	cout<<endl;
}
*/

string ret[]={
"DDDMDMDDDMMMMMDMMDDMDDMMDDMDDMMMMMDDMMDDMMMDDDMMDMDMDDMDDDMDDMDDDDDMDMDDDDMMMMMDDDMDDDDMDDMDDMDDMMMM",
"DDMDDDDDMMMMMMDMMMMDDDMMDDMMMMMDDMDDDDDMMDDMDDMDDDDMMMMDDDMDDDMDMDDDDMDDMDMDMMDDMMDMMDMDDDMDDDDMMMDMMDDDDDDDMDDDDDDDDDDDDMMDDDDMDDMDMDDMDDDDDDDMDDMDDDMDMDDDDMMMDDMMMDDDDDMMDMDMDMDDMMMDDDDMDDDMDDDDDMMDMDDDDMMDDMDMDMDDMDDMMDDMMDDDDDDMDDDDDDMDDDDDDMDDMDDDMMDDMMDDMMMMMMDMDMDDDMMMMDDMMMMDMDDDMDMMMDDMMMMDMMDMDDMDDDMDDDMDDDMDMDMMMMMDMDMDMDMDDDDDMDMDMDDDDDDDMDDMMMMDMMMMDDDDDDMMDMMMDDMDDDMDDMDDDMDDDMDMDDMDDDDDDDDDDMMMDDDDDMDMDMMDDMMDDMMMMMDMDDMDDMDDMMMDMDMMMDMMDDMDMDDDDDDMDMDDMDMDDMDMDDDDDDMDDDDMDMDDMDMDMDMDDDMMDMDDMMDDDMDDDMDDDDMDMDMDDDMMDDDDMMMMDDMDMDMDMMMMDMDDMDDMDDDMDDDDMMMMMMDMMDDDDMDMDDDMMMMMDDMDDMDDDMDDDDDDMDDMMMDDMMDDDDMDDMMDMDDDDDDMMMMDMMDDDDDDDDDMDMMDMDDDDDMDMMDDMDDDMDMMDMDDDDDMDMDMDMDMDMMDDDDDDMDDDDDMMDDMDDDDMDDMDMMDDDDDDDDMDMDDMDMDMMMDMDDDMDDDMMMDMMDDDDMDDDDDDMMDMDDMDDDMDDDDMDDDDMDDDMDDDDDMDDDDDDMDMDDMDMMMMMMMDMMMDMMDDDMDMDDDMMMDMDMMMDDMDDMMDDDMDMDDDDMMDMDDDDDDDMDMDDMMDDDMDDDDMDDDMDDDDDMMDDMDMDMDDDDMDDMMMMMDDDMDDMDMDMDMMDDDDDMDMMDMDDDDDDDDMDDMDMMMDDMDDMDMDMDDDMDDDMMMMMDDMDMDMMDDMMDM",
"DDDMDMDMMDMDMDDDDDMMDMDDDMDDDDDDMDDMDMDDMMMDMDDMMDDDDMDMDMDMDMMDMDDDDDMDDMMMMDMDMDDMDDDDDMMDDMDDMDDDDDMDDDMDDMMMDMMMMMDDDMMDDMDMMMMMMMDMMMDDMDMDDDDMDDMDMDDDMMDMMMDDMDMMMDMMMMDDDDDMDMMMDDDDDDMDDDMMDMDMMDMMDMDDDDDMMMMMDMMMMDMMDMDMMDMDDDDDMMMDDMDDMMDDMDMDDDDDDDDDDDMMMMMDMDDMMDDDDMMDMMDDDDMDMMMDMMMDDDMDDDDDDMMDMMMDMDDDDMMDMDDMMDMDDDMDMDMMMDDMDMMDDMDDDDMDDDDMDMMDMMDMDDDDDDDMMDDMMMMDDDMMMDDDDDDMDDDDDDDMDMMDMMMMMDDMMDMDMDDDMMMMDMDMDMDDDDDDMMDDDDMDDDDMMDDDMDMDMDDDDMMDDDDMMMMDDDMDDMMDDDDDMMDMMMDDMDDMMMMDMMDMDMDDMDMMDDMDMDMDMMDDDDDMDMMDDMMMDDDMMMDDDMMDDDMDMMDDMDMMMMDDMMMMMDMMDDMMMDMDDMMMDMDDDMDDDDDMDDMMDMMDMDMMDDMMMMDMMDMMDMDDMMDDMDDDMDMMDDMDMDDMMDMDDDDDMDDDDDMDDMMMDDMDMMDMMDMDDMDDMMDDMMMDMDDMDDMDMMMDMDDDMDMMMDDMMMDMMDDMMDMDDDDDDMDMDMDMDDDMDMMDMDDDDDDMDMMDDMDMMMDMDDDMMDMDMMDMMMDDDMDDMDMMMDDMMMMMDMDDMDMMMDDDDDDMMMMMMDDDMMDMMMMMMMMDDDDDDMMDDDDDMDMMDDMDDMDDDMDMMDDMMDMDDMMMDDMMMMDDMMDDDDDMMDMDDDDMDMDDMMMDDMMDDMDMDMDDDDMDDDDMMDDDDDDDDDDDDMMDMMMMMDDDMMDMDDDMDMDDMDDDMDMMDMDMMDDMMDDMMDMDDMDDMMMMMDDMMDDD",
"DDMMMDMDMDMMDDDDDMMMDDMMMMMDDDDDDMMDDMDDMMMMDMMMDMMDDMDDDDMDDDMMMMDDDMDMDDMMDDMMMMDMDMMDDDMDDDMMDDMMMMDMDMDDDMMMDDDDDDMMDDMDMDDMDDDMDDDDMMDMDMDDDDMDMDMDMMMMMDDDDDDDMDMMDMDDMDDDDDDDMDDDMMDDDMMMDDDDDDDMDMDDDDDDDDMDMMMMDDDMDDDMDDMMMMDDMDMDDDMDDDDDDMDDDDMDDDMDDDMMDMDDDDMMDDMMMDDMDMMDDDDDMDMDDMMMDDMDDDMMDDMMDMMMDDDDDMMMDDMMMDDMDDDDDMMMDDDDMMMDDDDDMMMMMDDMMMMDMDDDDMDMDMMDMDDDDMDDDDMMDDDMDDMMDMDDDMMMDMDDMDMMDDMDDDMMMMMMDDDDDDMDDDDMDDDDMMDDMMMMMDDDDMMDDDMMMMDMMMDMDDMDDMMDDMMMMDDDMDDDDDDDDDDDMDDDMDDMMDMDMDDDDMMDMDDDDDDMMMDDMMMDDDDDMDMDDMDDDDMMMDDMMDDDMDDDDDDMMDMMMDDDMMDMDDDMMDDDDMMDDDDMMDDDMDMMDMMDDMMDMDDDMDMDMDMDMDDDDMDDDMDMMMMDMDDDDDMDMMDDDMDMDMDMDMDMMMMMDDMDMDMDMDMMMDMMDDMDMMDDDDDDMDDMDDMMDDMMDDDDMDDDDMMDMDDDMDMDMDMDMDMDMMDMMDMMDMDDMMDMMDDDMMMDMDDDDDMMMDMDDDDDDDDDDDDMDDMDDMDDMDMDDMMDDMDMDDDDDMMMDDDDMMMDDMDDMDMMDDDDMDDDDDDMMDDMDDDDMMMDDDDMMDDMMDDDMMDDDMDDMMDDMDMMMDMMDDMMDMDMDMDDDMDDMMDMDDDDDMDDMMDDMMDDDMMMDDDMMMDMDMDDMMMMMDDMDMDDDMDMDMMDMDMDMMDMDDDDDDMDDDDDMDDDDMDMDDDDDDDDDDDMMMDDDMMDMDDDDDDD",
"DDMMDDDDMDDDDMDMDDMDMMMDDMDDDMDMDMDMDMMMDDDMDDDMMDMMMMMMDMDDDMDMMDMMDMDMDMMMMMDDDDDDMDMDDDMDDMDDMDDDDDMMDDDDMMDMMDMDDMDMDMMDDDMMMDMDDDMDDDDMMMDDMMMDMDMDDDDMMMMDDDMMDDDDMDDDDMDDMMDDDDDDDDDDDMDMDDDDMMDMDDDDDDMMMDDMMDMDDDDDDDMDDMDMDDDMDDDDMDDDDMMDMMDDMMMDMDMDMDDDDMDMMDMDMDMDDMMDMMDMDDDDMDDDMDDMDDMMMDDDMDDDDMDDMDDDMDMDMDDDDDDDDDDDMMDDMMDDDDDMDDDDDMMMMDMDDMDMMDDDDMDDMMMMMDDDDDMDDMDDDDDDDMDDDDMMDDMDDDMDMDMDDDDMDDMMDMDDMDMDMDMDDMDMMMDDDMMDMDMMDDDDDDDMMDDDDMMDMMDMMMMMMDDMDMMDDMDDMDMMDMDMDDMDMMDDMDDDMDDDDDMMDDMMDMMDMDDDDMDMMDDDDMMMDDMDDMDMDDDMDDMDDMMDDDMDMMDDDDDDDMMDDDDDDDDMDDDMMMDDDDDDDMMMMDDDMMMDDDDMMDMDDMDMMDMDDMDMMDDDDMDMMDDMMDDMMDMMMMDMDMDDDDDMMMDDMMDDMDDDMMMMDMMDDMMMDDDDDMMDMDDMMDDMMDMDDDDDDMMDDMMMMDDMDDDDDMMDMMDDDDMDDDDDDDMDDDDMDDDDMDMDDMMDDDDDDMDDDDDDDDMMMDDDMDDDDDDDDDMDDDMMMDMDDMDMDDDMDDMDDMDMDMDDDMDMMMDMDMDDDMDDDMDMMMMDDDMMDDDDMMMDDDDDMDDDDDMDMMDDDMDDMDMDDDDDDMMDMMMMMDDMDDDDDDDDMDDDMDDMDDMDDMDMMDMDDDDDDMMMMDMDDDMDDMDDDMDMDDDMDMDDDDDMMMDDDDDDMDMDMMDMMDDDDDMMMMMDDMDMDDMMMDDDMMMMMDDDDDDD",
"DDDMMDDMMDDDMDMMDMMMMDDMMMDDDDDDDMMDDDMDDDDDMDDMMMMDDMDDMMMDMDDMMDDMMMMDMDDDDDDDMDMDMMMDDDDDDDDMMMMDDDDMDDDMDDMDDMDMDDMMMDMDMMDMDDDDDDDDDMMMMMMMDMMMMDDDDMDDMMDMDDMMDMDDMMMDMMMDMDDMMMDDMMDDDDDDDDDDDMDDDDMDDDMMMMDDDMMDDMMMDDMDDMDMDMMMMMMMDDMDMDDDMMDDDMDDDDMMDDDDDMDDDDMMMMDMDDMMDDDDDDDDMDDMDDMDDDMMDDDMMMMMMMDDDMDDDMDDDMMDMDDMMDDMDDMDMDMDMMDMMMDDMMDMMMDMMMDMDMMMMMDDDDDMMDMDDDDMMDMMDMDDDMMMDDDMMMDDMDDMMDDDDDMDMDMMMDMDDMDMMDMDMMDDDMMMDDDMDDDMDMDDDDDDDDDMMMDDDDMMMMMMDDDDMMMDMDMMDMDMMDMMDDDDDMMMMMMDDDDMMMMDMDMDDDDMDMDMMMMDMMMMMDDDDDMDMMDMMDDMDMMDDDDDMDDDMDDDDDDMMDDMMMMMDMDDMDDDDDDDDDMMDDDDMDMMDDMDMDDMMMDDDMMDDMMDDMDDDDDDDDMMDDMDMDMDDDMMDMDDDMMDDMDMMDDDDDMMDDDDMDDMDMDDMMMDMMDMMDDMDMMMDMDMDMMDMMMMDMDMDDMDMDDDDDMDMMMMDMDDDDMMMDMMMMDDDDDMDDDMDDDDMDDMDMMMMMDMDDMDDMMDMMDDDMMMMDDDMDMMDDDDMMMDDMMMMMDMDDMMMMDMMMDMDDMMDMDMMMDMDDDDMDMDMMMDDDMDMMDDMMDMDMMMMDDDMDDDMMDDDDMMDDMDMDMDMMMDMDDMDDMDDMDDMMDMDDDMMDDDDMDMMDMDDDMDMMDMDDDMDMDDDMDDMMDDMDDMDDMMDDMDDDMDDMMDDDMDMMMDDDDDMMDMMDMDMMDDMMMDDDMDDMDDMMMMDMMMDDDD",
"DMMDDDDMDMDMMMDDDMDMMDMDDMDMDDDDDDMDDMMMMDMMDMMMDDDDDDDMDDMDDMDDMDMDDDDMDDDDMMMDMDDMDDMMMDDMDMMDDMDDDDDMDDMMDDMMMMMMMMMMDMMDMMDDDDMDDDMMDDDDDMDDDDMDDDDMDDMDMMMMMMDDMDDMMDDMMDMMMDDMDDDMDMDMDMMMDDMMDDDMDMMMDDDMMDDMMMDMMMMDMDDDDMDMDDMMDMDMMMDDDMDDMMMDDMDDDDDDMDMDDDDMDDDMDDMDDDDMDDDMMDDMDDDDMMDMMMDMDDMMDDDMDDMDMDDDDDDMMMDMMDDDDDMDDMDMDDDMDDDMMMDDDDDDMMMMMDDDMDDDDDMMMMMDDDDDDMDDDMDDDDMDMDDDMDMDDMDMMDMMDDDDMMMDDDDMDDDDDDDMDMDDDMDMMDDDMDDDMDMDDMDDDDDDDDDMMMMDMMDDMDMDMDDMDMDMDMMDMMMMMMDMDMMMMMDDDMMMDDMMMMDDMDDDDMMMDDDDMDMDMDDDDMDDDDDDMDMMMMDDMDDDMMDDDMMDDDMMMDMDDDDDMMDMMDDMMMDDMDDMMMDDMMDDDDDMDDDMDMMDMDDDDDDDDDMMDMDDDMMMDMDDMDMDDMMDMDMMMDMMDDDDMDDMMDDDMDDMMMDDMDMDMDDMDDDMDDDMDMDMMMDDMDDMDDDMMDMDMMDMMDDMMMDMDMMMMDDMMMMMDDDDDDDMDMMMMMDDDMMDDMMMDDDMDDDDMDDMDMMMDMMDDDDMDMDMMMDDMDMMMDMDDDDMMDDMDDMDDMDMMDMDDMDDDDDDDMMDDDMDDDMMMDDDDDDDMDDMMDMMMDMMMMDMDDDDDDDMDDDDDDMDDDDMDMMDMMMDDMMDDDMMMMDMMDDDDMDDMMDDDDDMDMDMMDMMMDMMDDMDDDDDDDDDDDMDMMMDDDMMDDDMDDDDDMDDDDDMMMDDMMMMDDDMMMDDDDMDDDMMDMMDMDMMMDDMMDDDMMMM",
"DDDMMDDMMMDDDMDDDDDDDDMDMDMMMDMDDMMDMMMDDDMDDMMMDMDDMDDMDMMMDDMDDDDMDDDDMMMDDDDDMMDDMDDDDDDMDDMMDDDDDMMDMDDMDDDDDMMDDMDDDDDMMDDDDDDMDMDMDMMDMDDDDMMDMDDMMDDMDMDDMDDDDMDDDDMDMDDDDDDDDDMMDMDDDDMMMDMDDMMDDDDMDDDMMDDDDDMMDDDMMMMMMMDDDMMDDMMDDMDMDMDDDDMMDMDDMMMDDDDMDMMDMMDMDDDMDDMDDMMDMMDDMMDMMMDDMDMMDMDMDMDMDMDDDDMMDDMMMDMDMDDDDMDMMDDMDMMDDDDMMMDDDDDDDDDDDMDDMMMDMMMDDDDDDDMMDDDDDMMDDMMDDMDDMDMDDMDMMDMDDMDMDDDMMDDDDMMMDDMDDMMDDMDDDDMDDMDDMMMDDDMDDMMDMMMDDMDMDMMMMDDMMDDMDDDDDMMDDDMMMDDDMDDDDMMMDMDMMDDDDMDDDDMDDDMMMMDDDMMMDMDDMMMDMDDMMDDDDMMDDMDDDDDDDMDMDDDMMMDMDDDDDDDMDMMDMMMDDDDDMMDMMDDMDMMMMMDDMDDDDDDDMMDMMDDMMDMDDDMMMDMMMDDDDMDMMMMDDDMMDDDDDDDDMDMMDDDMMDDDDDDDMMDDDDDMMMMMMDDDDDMMMDMDMMDMDDMDDDMMDDMMMMMMMDMDMDDMMMDDDDDDDMDDMMDDMDMMMDMMMMMDDMDMMMMDDMMDMDMDDDDDDMDMMMMDMMDMDDDDDDDDMDMDMDDMDMDDDDDDMMMMDMMDMDMMDMDDMDDMDDMDMMDMMMMMMMDMDDMDDMMDDMMDMDDMMDDMMDMDDDDMDMMMMDDDMDMMMDDDMMDDDDDMDMMMMMDDMDMMMMMDDDMDDDMMMDDDDDDDMDMMDDDMMDDMDDDDDMMDDMDMMDDDMDMMMDMMDDMDMMMDMMMDMDMDMDDMMDDDDMDMDDMDDDDDDMDDMMDD",
"MDMDDMMDMMDDMMMMDMMMDMMDMDMDMDDMMDDDMDDDMMMDDDMMDDMDMMDDMDMDDDMDMDMMMMMMMMMMMMMMMMMMMMDDMDMDMMMDMDDMDMDMDDMDMMMDMDMDMDMMDMMMDDDMMMDMMMDDMMMMMMMDDMMMMMDDMMMDDMDMMMMMMDMMDDMMMDDDDDDDMDDMMDMMMMDMDMDDMDDDDDDDDDDDDMDDMDMMMDMMMMMMDDDMMDDMMMDMMDMMDMMMMDDMDMMMDDMMMMMDMMMMMDMDDDMDDMMMMMDDMDDDDMMMMDDDDMMMMMDMMMDMMDDDMMMMDMMDMMDDMDDMMDDMDDMMMDMDMDDDDDMDDMDDMMMDMMMMDDDMMMDDDDMDDMMMMDDDDMDDMMMMDMMDMMDDMMMMMDDMDDMMMDMMMDMMMDMMMMMDMMDMMMMMDMMDDMMMDMDMMMMMMMMMMMMDMDMDDMMDMDMMMMDMDMMDDMMMDMMDDMMMMDMMMMMMMMDDDMMDMMMMDMMMDMDDDDMDDMMDMMDMDMMDMDMDMMDDMMMDMMMMDMMDMMMMDDDMDDMMDDMDDDDDMMDMMDDDDDMMDMDMMDMMMDDMMDMMDMMDMMDMDMMMDMDMMMDDDDDMDMMDDMMDMMMMMMMMMMMMDDDDMDMMMMMMDMMDMMDMMDDDDDDDMDDMDMDMDDDMMDMMMMDMDDDMDDDMMMDMDMMMDDDDDMDMMMDMDDMMDMDDDMMDMDMMDMMMDMMMMDDMDDMDDDMMMMMDMDDMMMMMMMMMDDDMMDDDDMDMMDDDDDDDDMDMDDDMDMDDDMDMMMDMMDMMDMDDMMDMDMMDDMMDMDDMDMMMMMMMDMMMMMMDDMMMDMMDMMMDMMMMMMMDMMDDDMMDMDDMDDDMMMMDMDDDMMMDMDMDMDMMDMDMDMMMMMMMMMDDDDMDMDMDDMDMMMMDMDDDMMMMMMDMDDMMDMDMMMMDDMMMDMMDMMMDDDMMMDMMMDMDMDMDMMDMMMDDDDMM",
"DDDMDDMMDDMDMMMMMMMDMMMDMDDMMDDDDDMDDMDMMMMMMMDMDDDDDDDMMDMDDDDMDDDMMDDDMDMMMDDMDMMMDMDDMDMDDMDMDDDDDDMDDDMDMMMDMDMDDMMDMMDDDMDDDDMMDDMDDDMDDDMMDDMDMDMDDDMDDDDMDDMMDDMDMDDDMMMMMDDDMDMMMMDMDDDMDMMDDDDDDMMMDDMDDDMDMMDDMDMDDDDMMMDDMDDDMDDDDDDMMDDDMMMDMMDMMMMDMDDDMDMDDMDMMMDMMDMDDDDDMMMDMDDDMMMMMMDDDDMDMMDMMDDMDMDDMDDMDMMMDDDMMMMMDMMDMDDDDDMMMMMDDMDDMDDDDMDDDMDMMDDMMMDMDDMDMDMDDDMDDDDDDDMDMDMDDDMMMMMDMMMMDDDDDMMMMDDMDMMMDDDMDMDDDDMDDMDMMMDMDDMMDMMMMMDDMDDMMMMMDDMMDDMDDMDMDMDMDMDMDMMMMMDMMMMDMDDDDMMDDDMDDMMDMDDDDDDDMMDMDDDDMMDDDMMMMMMDDDDDDMDMMMDDMMMDDDMDMDMDMMDMMMDMMMDMDDDDMDDMDDMDDMDMMDMDMMMMDMMDMDMDDMMDMMDMDDMDDDMMDMDMMMMDMMDDMMMMMDDMMMDMMDMMMDDMDDMDMDMDDMMDMMDMDMMDDDMDDMDDDMDMDDDMDDMDDDMDMDMDMDDDMDMDDMMDMMDDMDDDDMDDDDMMMMDDMDDMMDDMDMMDMMMDMDDMDDDDMMDMMMMMDMDMMMDDDMMMMMMMDDDDDDMMMDDMDMMDMMMMDMMDMMDMMMDDMMMDMDDDMDDDDDDMDDDDDMDDDMDMMDMDMMDMMMMDMDMDDDDDMMMDMDDMMMDMDDDMDDDDMMDMDMDMDMDDDDMDMDMMDMDMMMMDDMDDMDDMDMDDMMMMDDDDMMDDDMMDMDDDMDMDDMMMMMDMMDMMDDDDDMDMMMDDDMDMMDDDMMDDMMMDMMMDMDDDMDMMDDDD",
"MDDMDDMMMMDDDMMMDMDMMDDMMDMDMDDDMDDMMDDDDDDDDDMDMDMDDDDMMMMDDDMDDDDMMDMMDMDMDDMDDMMDDDMMDMDMMDMMMMDDMDMDDDDDDDDDMDDDDMDDDMMDMDDMDDDMDMDDMMMDMMDDMDMMDDMDDDDMMDMMDMDMDDDDDMDDMDDDMDDDDDDMMMDDMDDDMDDDMDDDDMDDMDDMDDDDDMDDMMDDMMDDMDMMDDDMMMDMDDMMDMMDDDMMDMDDMMDMMDDMMMMMMDMMMMMMDMMMDDMDDDDDMMDDMDMDMDMDMMMDDMMDDMMMDMMDDMMDDDDMDDMDMMMDMMDDDDDMDMMDMDDMDDDMMDDDMMMDMMDDMMMMMMMDDMDDMDMDMMMDDDMMDDDMDDMMDDMMMMDMDDMMDMMDDMMMDDDDDDMDDMDDMDDDDDDDDMDMDDDMMDMDDDDMDMDDMDDDMDDDMDMDDDMDDMMDDMDDDDDMMMMDDMMDDDDDMDDMDDDDMMDMMMDDDDMDMMMMDMDMDMMDDMDMDDDDDMDDMDDMDDMDMDDMMMDMMMMMDDMMMDMDMDDMMMDMMDDDDDDDDMDDDDMDDDDDDDDDMDMMDDMDDDDDDMDDDDDDMMDDMMDDMDDDDDDDDDDDDMMMMDDMDDDMDDDDDMDMDDDDMDDDDDDMMMMMMDDMDMMDDMMDMDMMDMDMDDDDDDDMMMMDDMDDDDDMMMDDDDMDMMMMMDMDDDDDDDDMMDMDDDDDDMMDMDMDDDDDMMDDMMDMMDDDMDMDMDMDDDDMDDDMMDMMDMDDDDMDMDMMDMMMMDDMDDDMDMMDMMMDMDDMMDDMMDDDDMDMDMDMDDMMDMDDDMDDDDDMDMDDMDMDMDDMDDMDMMDDDDDDDDDMMMMDDDMMDMDMMDDDMDDDDMMDDDMDDDDDMDMDDMDDMDMDDDDMMMMDDMDDMDMMMMDDDDMDDDDDDDMDDDDDDMMMMMDDMMDDMDDDDDDDDMDMDDDDDDDMMDMD",
"DDDDMDDDDDDDMDDMMDMMDDDDDMMDMDMMMDMDDMDDDMMMMMMDDMMMDMDMDMDMDMDDDMDDDDMDDMMDDMDDDDMMDMMMDMDMDDDMDDMDDDDMDMMDDMDDMDDDDDMDMDDDMDDDMMDDMDDMDDMMDDDDDMDDDDDMDDMDDDDMDMDMMDDDDDDDDDMDMDDMDDMDDMMMMDDMDDDMMDDDDDDDDMMDDDDDMDDMDDDDMDDMDDMDMDMMMDMDDDDDMDDDMMMMDMMDMDDMMDMDMDDMDDDDDMDDDMMMMDDMDMMDMDDDDDMDDMMMDMMDDDDDMDDDMDMDDDDDMMDMDMMDMDDDDDDDDDMMDDMDMDDMMDDMDMDDDDDMMMMDDMMDDDDDDDMMDMMDMDDDDMDDDDDMDDDDDMDMMDDDMDMMDMMDMMMDDDDDDDMDMDMMMMMDDMMMDMDMDDMDDDMDMDMDDMDDDMDMDDDDMMMMDDMDDDDMDDDDDDMDMMDMMMMDMMDMDMDMDDDMDDDDDMDMDDDMMDDDMDDDDDDDMMDMMMMMMDMDMDDDMMMDMMDDMDMMDDDDDDDMMDDDMMDDDMMMDDDMDDDDDDDMMDMMDMMMDDDMMDMDDMMDMDDDMDDDDMDMDDDDMDDMMDMMMDDMMMMDMDDDDDMDDDDDMMMMDDDMMDMDMMDDMMDDDDMDDDMMDDMDDDMDDDDMMMDMMDMMDDMMDDMDMDDDDDMDMDMMDDDDDDMDDMMDDDMMMMMMMMDDMDDMMDDDDDDMMMMDMMDMMMMDDDDDMMMDMDDMDMDDDMMMDDDMDDMDDDDMDDMDMDMDDMMDMMDDMDDMDMDDDMMDDMDDDMDDDMMDMDMDMMDMMMMDDMDDDMMDMDMMMDDDDDDDMDMDMDDDMDDMMDDMMMMDDMDMDMDDMDMMDMMDDDDDDMMDDMMDDMDMDMMDMDDDDMDMDDMMDDMDMMDDDMDMDMDDDDDDMDMDMDDDMDDDDMMDMDDMMDDMDMMMDMMDDMDDDDDDDDDD",
"MDDMMDDDDMDDDDMMDMMDDMDMMDMMDDMDDDMMMMDMMMDDMMDMDDMMDMDMMDDMMMDMMDMMDMMMMMDMMMMMMDMDMMMDMMDMDMDDDMDDDDDDMMMDDDMDDMDDMMDDDDMDDMDMDMMMMMMDDMDDMDMDDMDDMDMDDDDMMDMMMMMMDMMDMMDMDDDMMMDDDDDDMMMDDDMDDMDMDMDDDDMDDMMMMMDMDMDDDMMMDDMDDDDMMMDDMDDMDDMDMMDMDDDMDMMMMDMDMMMDDMDDMMDDMMMMMDDMMMDDMDMMMMDMDMMMDDDMMMMDMMDDDDMDMMMDMMDMMMDDMDMDDMDMDMDMDDMMMMMDDMMDDDDDDDMMDMDDMMDDMDDMDMMDDDMMMMDMMDMDMDMMDMDDMDDMMDDMMMMDMMDDMDMDMDMMDDMDDDDMDDDDDDDDDDDMMDDMDMMDMDMMMDDDDDDMDDMDDMDDDMMMDMDMDMDMDMMDMMMDMMDDDMMDMDDDDDDMDMDDMDDDDDDDDMMDDMMDDMMMMMDMMDDDDDDMMDDDDDDMDMMMDDDDDDDMDDMMMDDDDDMDDDMMDDMDMMMDDDMDMMMMMMMDMMDDDDDMMDDMDMDMMMMMMDDDMDDMMMMMDDMDMMDDDMDDMMMMMDDMDDDDDMMDMMMMMDDMDMDMDMDMMMDDMMDDMDDDMDDMDDMDDDDMDMMMMDDMDMDDMMMDDDDMDMMMMMMMDMDMMDDDMDDDMDDMDMMDDMDMDDMDMDMDDDMMDMDDMMMMMMMDDMMDDMDMDMDDMMDDMDMDDDMMMMMDDMMMMMMDMMMDDMDDDDMDDMDMMDMMMDMMMDMDMMDMDMDMDMMDDDMDDDMDDDDMDMDDMMMMDDDMMDMDDMDMMMMDMDMMMDMDMMMMDDDDDMDDDDDMDMMMDMMMMDMDDDDDMMMDMDDMDMDMMDMMMDMMDMMDDDMMDDDMDDMMMDDDDMMDDMDDMMMMDDMMDDDMMMDMDDMMMMDDMMMDMMDDDMDD",
"DMMMMMDDDDMDMDMDDDMMDMMMMDDMDMMMMDMDDDMMDMDMDMDDMMMMMDMDDMMMMDMDMDDMMMMDMMMMMMMMMMDMMDDDMMDDMDMDMMDDDDMMMMDMMDDMMDMDMDMDDMDMMDDMMMDMMDMDDDDMDMMMMDDDMMMMMMMDMMMDMDDMDDDDMMDDMDDDMDDDMDDMMDDMDMMMDDMMMMMDDMDMDMMDDMDDDDMMDDMMMMDDDMMDDMMMMMMMMMDDMDMDDMMMDMDDDMDMMMDMDDDDMMDDDMMMDMMDMMDDDDMMDDMDDDMMDMDDMMMMMMMMDDDDMMMDMDMDDDMMDDMDMDMDDMMMMMMMDDDMMDDMDMDDMDDMMMDDMMMDMDMMDDDDMDMDMMMDMDMMMMMMDDDDMMDDMDMDDMMMMDDMDDMDDDMDDMMDDMMMDDMMDMMDMMDMMDMDMMDDMMDDMMDMDDDDDDDDMDDMDMDMMDMMDDMMDMDDMMMMMMMMDMMMMDDDMDDMDDMDDDDDDDMDMMDMDMDDMMDMMDMMDDDDDMMMMDMDMMDMMDMDDDMMDMMDMDDMMDDMDMDDDMDDDMMDMDMDMMMDDMMDMDMDMMMDDMDMDDMDMMDDDDMMMDDDDDMDDDDMDMMMDMDMDDMMMMDMDDDDDDMMMMDDDDDMMDMDDMDDDDDDDMMDMDMMDMDMDDMDMDDDMDDMMMDDDDMMDDMDDMMDMMMMDMDMDDMDMMDMDMMMDDDMDMDMMMMMDDDDMMMMDMDMDMMMMDDMMDDDDMMMMDMDDMDMMDDMDDDDMMMDDDDDMDMMMMMDMMMDMDMMDMMMMMMMMMMMMMMMMDDDDDMDMDMMMMDMDMMMDDMDMDDMMMDMDMDDMDDDDMMDMDMMMMDMDDMMMMMMMDDDDDDMMMMDDMMMDDMMMDDMDMMMMMDDDDMDMDMMDMMMMMMDDDDDMDMDMMMDMMDDMMDDMMMMMMMMMMDDMMMMMDDMDMDMDDDMDDDMDMMDDDDMDDDDMMDDDDDD",
"DDMDDDMMDDMDMDDMMMDMDDDMDMMDMMDMMMDMMMDMDDDDDMDMMMMDMDDDDMDMDDMMMDDMMMDDDDDDMDMMMDDDMMDDDMMMMDDMDMMMMMMMDMMDMDDDMDMDMMMMMMDDMDMDMDMMMDMMMMDDMMDMMMMMDDDDDDMMMMDDDDMDDDDDMDDMDMMMMDMDDMMDDMMDMMMDMMDMMMMDMMMDMMDMMMDMMDMDDMDMDMDMMMDDMMMMMDMMDDDMMDDMMMMMDDDMMMDMMMDMMDMMDMMMDMMMDDMMDMDDMDDDDMMMDDDMMDMDDMDMMDDMMMDMMMMDMDDDMMMDDDMMMDMMDMMMDDDDMMMDDMMMDDDDMMMMMMMMMDDMDMDDMMDDDMMMMDMDDDMDDDMMDDMDDDDDMMDDMDDMMMDDDDMDDDMMDMDMMDMDMDMMDDMMMDDDMDMDDDDDDMMDMDMDDDMDDMDMMDMDDMDMMMDDMDDMMDMMMMMMMMDDMMDMDMMMMDMDMMDMDMDDMMMMDDMMDMDMDDDDMDMDDMMMMMDMMDDMMMDMMMDMDDDMMDDDDMMDMDMMDDDDMMDMDDDMMMMMMDDMMDMMDMDMMDMMMMDMDDDMMMMMDDMMDDDDMMDDDMDMDMMMMMMDDMDMDMDDMDDDMMDMDDDDMDMMDDMDDDDDMMDDMMDMDMMDMDMMMDMMMMMMMDDDDDDDMDMDMMMMMDMDMDDDMMMDDMMMDMDMDMDDDMDMDMDDDDMMDMMDDDMMMMDDMDMMDMMMDDMDMDDMDMMDMMDMMDMMDDDDMMDMDMMMDDMMMDMDDMMDMMMDMMDDMDMMDMDDDMMDMMMMMDMMDDMDDDMMMDDDDMMMMMDMMMMMDDMMDMMMDDMDMMDMMMMMDDMMDMDMDDDMDMDDMMDDMMDDMDMMDMDMDMMMMMDMMDDMMMMMDMMMDMDDDMMMDDMDDDMDDMMMMMMDMMMDDMDDMMDDMDDDDMDDMMDMMDMMMMMDDMDDMMMDMDDDMDDDDMDD",
"MMMMMDDMMDMDMMMMMMMDDMDMDMDDDMMDMDMMMDMMMMMMDDMDMMDMMMMDMMMDDDMMMMMDDMMDMDDMMDMDDMMDMDMMMDMMMMMMMDDMMMDDDMDDMDMMDMMMMMDMMDMMMMMMDDMDMDDMDMDMMDMDDDMMMMMDDMMMMDMMDMDDDDMMMDMMMMMMDDMMMMDMDMMDDDDMMMMMMDMMMMMMMDDMDMDMMDMMMMDDDMDDMMDMMMDDMMDMMMMMMDMMMDDMMMMMDDMMMMMMMMMDMMMMDDMDMMMMMMMDDDMDDDDMDMMDMMMDMDDMMDMMDDMMDMDDDDDMMDDDMDMDDMMMDDDMDDMMMMDMMDDMMMMDMMMMDMDDDMMDDDDMMMDDDMMMMDMMDMDMDMDDMMDMMDMMDDDMDDMDMMMDMMMMMDMMMMDDDMDMDDMDDMDDMMDDDDMDDMMMDDMMDMDDDMMMMMDDDMDMMMMMMDDMMMDDMDMMMMMMMDMMMDMMDMDMMMDMMDDMMDDMMDDDDMMMMMMMDMDMMMMMDMMDMMDDDMMMMMMDDDDMMMMMMMMMMMMMMMDDMMDMDMDDMMMMDMDMMDMDMDDMDDDMMDDDMMMDMMDMMMDDMMDDMDDMMDDDMMDDMDDMDMMDDDMDMMDMDMMDMDDDMMMMMDDDMMMDMDMDDDDDDMMMMMDDMMDMDMMMMDDDDMDDDMMDMMMDMMDMMDDMDMMDDDDDMMMDMDMDMDDDMDMMDMDMMDDMDMDDDMMMMDDMDDDDMMDMMMMDDMMDDDMDDDMMDMMMDMDDMDDDMDDMMDMMDDDMDMMDMDMDMMMMMMMMMMDMDDMMMMDMMMDDMDMDMDMDDMMMDDMMDMDMMDDDDDMDDMMMMMDMDMDMDDMDDDMMMMDDMDDDDMMDMMMDMDDDDDMMMMMMDMDDMMMDDDDDMMMMMMMMDDMDMMMDMMDMMDMMMMMDMDDDMMDDMDMMMMDDDDDMMDMDDMMDMDMDMDMMMMMMDMDMMDDDMMDMDDMM",
"MMDMDDDMDMDDMDDMDDDMDDMMMMDDDMDDDDMMDMMMMMDDMMDDDMMDMDDMMMDDMDMMMMMMMMMDMMDDDMMDMDMMDDDMMMDDDDDDMMDMDDDDMMMDDMDDDMMMMDDMDMMMDDDDDDDDDDDMMDMMDMMDDDMDDMMDMDDDMDMMDDMMMMDMDMDDDDMMMMMDDDDDDMDMMMMMMDMMDMDMMDMDMMDDDDMMDDMDMDMMMMMDDMMMMDDDDDMDMDMMDDDMMDDMMDMMDMMDDDMDDMMDDDMMDDMMMDDMMDDDMDDMMDDMMMMMMMDMMMDMDDDMMDDMMDDDMMMMMMMDMDDDDMDMDMMDDDMDMDMMMMMDMDDDDMDDDDMMMMDMDDMDMDMMDMMMDMMDDMDMMDMMDDMMDDMMDMMMDDDDMMMMDDMMDMMMMMDMMMDMDDMMMDDMDDDMDMMMMMMDMMMDDMMDDMMDMDDMDMDDDDMDMDMDDMDMDMDDDDDMDDMDMDDMMMDDDMDDMDMDDDMDMDMMMDDMMMMDDDDDDMDDMDMDDDDDMDDDMMMMMMMMMDDMDMMMDMMDMMDDDDMDMMMDDDMDDDDMMDDMDMMDDDDMMDDMMMMDDMDDDDDDDMDMDMDMMMDMMMMMDMDDDDDMDMDMDDDMDDDMMMMMMDMDDDDDDMMMDDMMDMMMDMMMMMDDDDDMDDDDMMDDMDDDMMMDMMMMDDDDDDMDMDDDDMDMMDMDDDDDMMMMDDDMMDMDDMMDMMDDDMDMDDMMMDMDMMMMMDMDDMMDMMDMDDDMDDMDDMMDMMDDDDMMMDDMMMMDDMDMDDMMMDMDMMDDMMMMDDDDMMDMMDMDMMDMMMMMDMMDDDDMMDMMDMDMMDDMMMDMMMDMMDDDDMDDMDDMDMDMMDMMMDMMMMMMDMDMDMMMDMMDMDMDDDMDMMMMDDDMMDDDDMMMDDMMMMDDMMDDMDDMMMDDDMMMDMDMMMDMDDDDMMDMDMMDDMDMDMDMDMDMMDDMMDMDDMDDDDDD",
"MDDDMDMMMDDDDDDMMDMDMDMDMMDMMDDDDMDMDDDMMMDMMDDMMDMMDMDDDMDDMDMMMMDDDMMDMDMMDMMMDMMMMDDDMDMMDMDDMDDMDDMMMDDMMMDDDDDDMDDMDDDMDMMDMDDDDMDMMMDDDDDMMDDMMMMDDDDMMMMMMDMDMMDMMMMDDDDDMMMDMMMMDDMDMDDMDDDMMMDDMMDDDDDMDMDMMDMDDDDMMMMDMMMDMMMMDMDDDDMDMDDMMMDMDMDDDMDMDDDDMMMDMDDMDMDDMDDDDMDDDMDMDMDMMMMMDMDDDDDDDMMMDDDMMDDMMDDMDDMDDMDMMDDDDDMDDDDDMDMDDDDDMDMDMDDMDDMMDMMMDDDDMDDDDDMMDMDMMDMDMDMDMDDMMMMDDDMDDDDDDDMMDDMMDDMMDDMDDMDMDDMDDDDMDDDMMDDDDDMDMDDDDDMMDMDDDMMMDDMMMDDDMMDMMDMMMDMMMMMDDDDMMDMDDMMDMMMMDDMMDDMDDDMMMMMMDMDDDDDMDMMMMMDDMDMMMDDMMDDMDMMDMDMMDDMMDDMDDDDMMDDDDDMMDDDMDMMMMMMMMDMMDMDDDDMDDMMMDMMDDMMMDDMDMDMDDDMMMMMDMDDMMDDDMDDDDMDMDDMMDMDMMDDMDDDMDDDDMDDDDDDDMDMMDDMMDDDDDDDMDMDDDMMDDMDDMDMDMDMMMDDDMMDDDMMDMMMDDDDMDDMDDDMMMDDDDDDMDMDDDDMMMDDDMDMDDDDMDMMDDDMDDDMDDDMDMMDMMDMDMDDDDMDDMDMDDMDMDDDDDDMDMDDMDDDMDMMDMDDMMDDDDMDDMDMMMMDMMDDMDDDMDDDDDMMDMMDMDMDDDMDMDMDDDDDDMDMMDDDMDDMDDDDMMMDMDMMDDDMMDDMDMMDDDDMDDDDDMMMDMDMDMDDDDDMDMDMMMMDMDMMDDDMMDMMDDMDDDDDMDDMMDMDDDMDDDDDMMDMMMMMDDMMMMDDDDDDDDDDD",
"DMDDDDMDDMDMMMDDMMMMDDDMDMMDMMDMDMMDMDDDMDDMDDMMMDDMDMDMMDDMMMMMMDDMMMMDMMDMMDMMDDDDDMMDDMMMDMMDMMDMMMDMDMDDMDDMMDMMMMDMDMMDMDDMMMMMDDDDMDMMMDMDDDDMMDMDDDDDDDMDDMMDMDDDMMMMDMDMDMMDMMDMDMMDDDMDMMMDDMDMDDDDMDMDMMDDDDMMMDDMDMDMDMDMMDDDDMDMMMDMMMMMMDDMDDMMDMMDDMDMMMDDDMDMMDMMMDMMMDMDDMMMMMMMDMMMMMDMMMMMMDDMMMMMMDMDMMDMDMDDMDDMDMMDDMMDDMMMMMMDMMMDMMMDDDDMMMMMMMMDDMMMDMMMDMDMDDDMMDMDMDMDMMDDMMMMMDDDDDMDDDDMMMMDDMMMDDDDMMDDDMDMMDDMMMDDMDMMMMDMDDDMDDDDMMDDDDMMDMDMDDMMMMDMDMMMDMDDMMMDMMDDDMDMMMDDDMMMDDMMMDMMMMMDDMMDMMMMMMMMMDDMMMDMMMDMDMMMDMMDDDMMDDDMDMMMMMDDDMMDMDDMMDMDMDDDDDMMDDMMMDMMMDMMMMMMMMDMMMMDDMMDDDDMDDMDMDDMDMDMDMDMMMDDMMDMMDMMDDMMDMMDMDMMDMDMMDMDDMMDMMDMDMDMDMMMDDDMMDMMMMMMDDMMDMDMMDMDMDDMDMDDDMDMDMMDDMMDMDMMMMDDMMDDMDMMMMDMMDMDMDDMMMDDMMMMDDMMMMMMMDMMMMDMMDDMMMDDMDMDMMMMMDDDMDDMDMDMDMMMMMMMDDMMMMMMMMMMMDDMMMDMDMMDMDMMMMMDMMMDDMMDMMMMDDDMDDDDDMDMDMDDMDMMDDMDMMDMDDDDDDMDMMDMDMDDMDDMDDDMMMDMMMMMMDDMDDDDMMMMMDMMDDMDMDDMDMDDMDDDMMMDDDMDMMMMMMDMDMMMDMMDMDMDDDDDMMDMMDMDMDDDDDMMDDMMMMMDDDDM",
"DMDDMDDMDMDMMDMDMDMDMDDDDDDDDDDMMDDDMDDMMDMDDDDDDMMMDMMMMDMMDDMMMDDMDMDMDDDMMDMMMDMDDMDMDMDDDDDMMDDDDMMMDMDMDDMMDMDMMMMDDMDMDDMDDDDDDDMMMMDMMDMDDMDDDMDMDDDDDMDMMDDDMDDDMDDMDDDMMDMDDMMDMDDMDMMMDDMMDDDDMDMMMMDMMDDDMMMDMMDDMMDDDDDDDMDDDDDDMDDDMDDDDDMDMMMMDDMMDDDMMDDMDMMMMDMDMDMMMDMDMMDDMDDDMMDMDDMMDMDDDMMDMMDDMMMMDDMDMDMMDDDDMDMDDDMMDMDMDDDMMMMDDDDDDMDDMMDMMDMDDDDMDDDMDDDDDMMMDDDDDDDMMDMDDDDDMDDMDDMDDDDDMMDMDDDMDDMDMDDDDDDMMDMDMMDDDMDDMMDMDMDDDDDDMDDDMMMMDDDDDDMMMMDDDMDMDDMMDDMMMDMDDMDDDMDDMMDDMMMDMDMMMDDDMMDDDMDMDDDDMMMDDDMDDMDDMDDMDMMDMMDDDMMMDMDDDDDDDDDDDDDDDMDMDDDDDDMMMDMDMDDDMMDMDDDDDDDDDMDMDMDDDMMDDDDDDMDDDDMDDDMMDMDMDDMMDMDMMMDDMMDDDDDDDDDDMDDDMDMDDMDDMMDDMDDMDMMMMMDDMMMDMDDDDMMMMMMMDDDDMDDDDMDDMDDDDDDDMMMMDMDDMDDDDDMMDMDDDDMDMDDDMMMDMMDMDMDDMDMDDMMDMDMDMDMMDDDMDDDDMMMDMDDDMDDDDDDMDMMMDDDDMDMMDDDMDDDMDMMMMMDDMMMMDMMMMDDMDDMMMDDMDDDDDMDDMDMDDDMDDDMDDMDDDMDDMDDDDDMMMMDDDDMMDMDMMDDDDMMMDMDMDDMDMDMDMDMMMMDDDDMDMDDDMMMMMMMMDDDDDMDDDDDDDMMDMMMMMDDDMMMDDMMMMDMDDDMMDDDDMDDDDMDDMMDDDMDDDMDM",
"MMDDMMMMMMMMMMMDMMMMMMDMDMDDDMDDMMMDMDDMMMMMMMDMDMDDDDMMDMMMMMDMMMMDMMMMDMMMMMDMMMMMDMDDDDDMMDMMMMMDDMMDMDMMMMMDDMDMDDMDMMMDMMDMMDDMDDDMMDMDMMDMMMMMMMMMDMMMDMDDDDMMDMDMMMMMMMMMMDMMMMDDMDMDDMMDMMMMDMMDMDDMDMMDMMDMMDMDMDDMMMMDMMDMDMMDDDDMDMMMMMMMMMMMDMMMMDMDDDMMDDMMMDMDDDDDMDMMMMDDMDMMDDMDDDMDMMDDMMMDMMMDMMMDDDMMDMMDDDDMMDDMDMMMMDMMMMMMDDDMMMMDDMMDMMMMDMMMDDMDDMMMDMMDMDMMMDMDMDMDDMDDDMMMDDDMDMMMMMDDDMDMDMDMDMMMMMDDDMMMDMMDDDDDDMDDDDMMMMMMDMDMMMDMMMDMMDDDMMDDMMMMDMMDDMMMDMMDDMMMMDDDMDMDDMMMDDMMDMMDMMDDMMDDDDMDMMMMDMMMMDMMDDDMMMDMMDDDDDDMMMMDDDDDMMMDMMMDMMMMMDMMDMMMDMDDDMDMDDMMDDMDMDDDMMDMMMMMDDMDMDDMMMMDMDDMMDDMMDMDMDMMDDMMDDDMMDDMMDDMMMMMDMMMMMDMMDDMDMDMMDMDDMMMMMDDMDMDMMDMMDMDMMMMDDMMMMMDDMMMMMMMDMDMDMDDDMMDDDDMMMMDMMMDMMDMMDDDMMMMDDMMMDMMDDMDDMMDDMMDDMMMMDMMDDMDDDDMDMMDDMMMMMMDDMDDMMDDDMDDMDMMDMMMMMMMDDMDDDMDDMMMMMMDMDDDDMMDDMMMMMDMDMDMMMDDMDMMMDDDDMMMDDDMMMDMDMDDMMMDDDMMMMDDMMDMMDMDMMDMDDMDMMMMMDDDDMDMDDMMMDDDMMMDMMDMDDDMDMDMDMMMMDDDDMDMMDMMMMDDDMMDMDDDMMDMMMMMDMDDDMDMDDMDDMDDDMDDMDDD",
};

class TwoMazeAlgorithms {
	public:
	string classify(int TID) {
		return ret[TID];
		
	}
}

まとめ

自分は行き止まりの位置関係をカウントしたが、Nが小さいときはダメだったようだ。