Codeforces #220 Div2. C. Inna and Dima

CF220に参加。Div2の割に問題が難しいうえ、ミスジャッジでUnratedになるなど色々残念だった回。
でも問題は結構面白いんだよなぁ。
本番はAはHackを食らい、Bはまぁ誤ジャッジでpretest通らず、Cは変数名ミスでWA、DはTLE、Eは間に合わず、と散々だった回。
Unratedで良かった…。
http://codeforces.com/contest/374/problem/C

問題

D,I,M,Aのいずれかの文字が書かれたグリッドが与えられる。
任意のマスから初めて隣接マスをたどった場合、"DIMA"という文字列を最長何回繰り返すことができるか答えよ。

解法

まず、全てのDに対し、1回分"DIMA"とたどる手順および、1回DIMAとたどったうえで次に別の"D"に到達する手順があるかを列挙する。
マスの数が10^6に対し、最大で４方向への移動を４回で計4^4通り程度計算する必要があるが、実際はDIMAとたどれる手順はそこまでは多くない。

上記手順が終わると、後は任意の"D"を初めて何回次の"D"に移動できるかをDFSで求めればよい。
閉路を見つけた場合は、無限回"DIMA"をたどることができる。

int N,M;
set<int> okok[1001][1001];
set<int> rev[1001][1001];
int fin[1001][1001];
int cost[1001][1001];
string S[1001];

int dfs(int y,int x) {
	int r=0;
	if(cost[y][x]>=1<<30) {
		_P("Poor Inna!\n");
		exit(0);
	}
	if(cost[y][x]>0) return cost[y][x];
	
	if(okok[y][x].empty()) {
		cost[y][x]=fin[y][x];
	}
	else {
		cost[y][x]=1<<30;
		ITR(it,okok[y][x]) r=max(r,dfs(*it/1000,*it%1000));
		cost[y][x]=1+r;
	}
	
	return cost[y][x];
}

void solve() {
	int f,i,j,k,l,x,y,r,rr=0;
	int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},ty,tx;
	cin>>N>>M;
	FOR(y,N) cin>>S[y];
	l=0;
	FOR(y,N) FOR(x,M) if(S[y][x]=='D') {
		FOR(i,4) FOR(j,4) FOR(k,4) {
			int x1=x+dx[i],y1=y+dy[i];
			int x2=x1+dx[j],y2=y1+dy[j];
			int x3=x2+dx[k],y3=y2+dy[k];
			if(x1<0 || x1>=M || y1<0 || y1>=N) continue;
			if(x2<0 || x2>=M || y2<0 || y2>=N) continue;
			if(x3<0 || x3>=M || y3<0 || y3>=N) continue;
			if(S[y1][x1]!='I') continue;
			if(S[y2][x2]!='M') continue;
			if(S[y3][x3]!='A') continue;
			l=fin[y][x]=1;
			FOR(r,4) {
				int x4=x3+dx[r],y4=y3+dy[r];
				if(x4<0 || x4>=M || y4<0 || y4>=N) continue;
				if(S[y4][x4]!='D') continue;
				if(y4==y && x4==x) return _P("Poor Inna!\n");
				okok[y][x].insert(y4*1000+x4);
				rev[y4][x4].insert(y*1000+x);
			}
			
		}
	}
	if(l==0) return _P("Poor Dima!\n");
	FOR(y,N) FOR(x,M) if(S[y][x]=='D') {
		if(cost[y][x]) continue;
		l=max(l,dfs(y,x));
		if(l>=1<<30) return _P("Poor Inna!\n");
	}
	
	_P("%d\n",l);

}

まとめ

ちょっと実装が面倒だった。
"DIMA"の検出は4^4通り総当たりしてるけど、意外と実行時間は余裕でした。
閉路検出は以前もCodeforcesで何度か出ているね。