Codeforces Round #224 (ディビジョン 2) D ブルート フォース検索と memoization_html/css_WEB-ITnose

半年くらい質問を読んでいますが、私の英語は下手すぎます 質問の意味はチェスの駒を2つ開始点としてチェス盤に置くことですが、開始点を#にすることはできません。画像の指示に従って移動を開始します。上に移動し、下に移動します。目の前に # がある場合は、その指示に従ってください。歩いている間は 2 つのチェスの駒が互いに接触することはできませんが、最終的には同じ # に到達します。ここでは問題ありません。無限のステップを実行できる場合は、たとえば < と出力します。 ; このようにして、無限に左、右、左に移動し、2 つのチェスの駒がとった最大ステップ数の合計を尋ねることができます

一 -1 を出力することで行き詰まり始めました。 .> に加えて円を形成することもできますが、これは判断が難しく、画像が 2000 * 2000 なので、逆 DFS は書きませんでした。このように、(i, j) を起点として取り得る最も遠いステップ数をメモリ内で検索する以外に方法はありません。ここで、画像が 2000 * 2000 であるため、2 つのチェスの場合、最大 4,000,000 ステップを実行できます。ピースが互いに続く場合、最大でも 8000000 を超えることはありませんので、最大値 MAXN = 8000000 を設定できます。通過点であるマークされたポイントに戻ると、この値が返され、それは -1 です。

開始点として各点を検索します。最大歩数を超えた後、同じ最大歩数の 2 つの点があり、歩行プロセス中にそれらが衝突しない場合、その合計が計算されます。最大ステップ数は ans + ans です。見つからない場合は、2 つのチェスの駒を順番に配置するのが最適な結果です。つまり、ans + ans - 1 です。これがディープサーチのコードの実装です。書くのは少しややこしいですが、

const int MAXN = 8000000 + 55;char aa[2000 + 55][2000 + 55];int mp[2000 + 55][2000 + 55];int xx[5] = {-1,1,0,0};int yy[5] = {0,0,-1,1};int dis[2000 + 55][2000 + 55];bool vis[2000 + 55][2000 + 55];int bb[2000 + 55][2000 + 55];int n,m;int ans;void init() {	memset(aa,0,sizeof(aa));	memset(mp,0,sizeof(mp));	memset(dis,-1,sizeof(dis));	memset(vis,0,sizeof(vis));	memset(bb,-1,sizeof(bb));}bool input() {	while(scanf("%d %d",&n,&m) == 2) {		for(int i=0;i<n;i++) {			scanf("%s",aa[i]);			for(int j=0;j<m;j++) {				if(aa[i][j] == '#')mp[i][j] = -1;				if(aa[i][j] == '^')mp[i][j] = 0;				if(aa[i][j] == 'v')mp[i][j] = 1;				if(aa[i][j] == '<')mp[i][j] = 2;				if(aa[i][j] == '>')mp[i][j] = 3;			}		}		return false;	}	return true;}bool isok(int x,int y) {	if(x <0 || x >=n || y < 0 || y >= m)return true;	return false;}int dfs1(int x,int y) {	if(isok(x,y))return 0;	if(vis[x][y])return MAXN;	if(dis[x][y] != -1) return dis[x][y];	vis[x][y] = 1;	if(mp[x][y] == -1) {		vis[x][y] = 0;		dis[x][y] = 0;		return 0;	}	else {		int tmp = dfs1(x + xx[mp[x][y]],y + yy[mp[x][y]]) + 1;		vis[x][y] = 0;		dis[x][y] = tmp;		return tmp;	}}int dfs2(int x,int y,int cnt) {	if(bb[x][y] != -1) {		if(bb[x][y] == cnt && mp[x][y] != -1)return 0;		return 1;	}	if(mp[x][y] == -1) {		bb[x][y] = cnt;		return 1;	}	else {		bb[x][y] = cnt;		return dfs2(x + xx[mp[x][y]],y + yy[mp[x][y]],cnt + 1);	}}void cal() {	ans = 0;	int mark;	for(int i=0;i<n;i++) {		for(int j=0;j<m;j++) {			if(mp[i][j] == -1)continue;			if(dis[i][j] != -1)continue;			int tmp = dfs1(i,j);			if(tmp >= MAXN){ans = MAXN;return;}			ans = max(ans,tmp);		}	}	if(ans == 0)return ;	mark = 0;	for(int i=0;i<n;i++) {		for(int j=0;j<m;j++) {			if(dis[i][j] == ans) {				if(dfs2(i,j,1))mark++;				if(mark > 1){ans *= 2;return ;}			}		}	}	ans += (ans - 1);}void output() {	if(ans >= MAXN)puts("-1");	else cout<<ans<<endl;}int main () {	while(true) {		init();		if(input())return 0;		cal();		output();	}}