Codeforces Round #224 (Div. 2) D Brute force search plus memoization_html/css_WEB-ITnose

I have been reading the question for half a year, and my English is terrible. The meaning of the question is to place two chess pieces on the chessboard as the starting point, but the starting point cannot be on #, and then start moving according to the instructions in the picture, < left> right ^Up v Down, when moving, you can only follow the instructions in the picture. If there is a # in front of you, you can walk in, but you can't walk anymore. The two chess pieces can't touch each other while walking, but they will both move in the end. It's okay to go to the same #, and if you can take infinite steps, output -1, for example > < In this way, you can move left and right infinitely, and then ask you the sum of the maximum number of steps taken by the two chess pieces

I was trapped by the output of -1 at first, because in addition to... When writing dfs, the image is 2000 * 2000, which is a bit big. I didn’t expect reverse DFS. I have no choice but to perform a memory search. Let dis[i][j] represent the steps that can be taken from (i, j) as the starting point. The furthest number of steps, so that the time should be able to pass, and then enumerate each point as the starting point for in-depth search, here you can judge whether it is -1, because the picture is 2000 * 2000, so you can go up to 4000000 The number of moves, if two chess pieces move in tandem, will not exceed 8000000 at most, so you can set a maximum value MAXN = 8000000. Once the marked point is moved again, this value will be returned, and the judgment can be made. Whether it is -1,

After finding the maximum number of steps for each point as the starting point, start searching. If there are two points with the same maximum number of steps, and they do not collide during the walking process, then The maximum sum of steps is ans ans . If you can't find it, placing two chess pieces one after another will definitely be the optimal one, which is ans ans - 1. Okay, here is the implementation of the code. The deep search is a bit confusing,

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')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= MAXN){ans = MAXN;return;}			ans = max(ans,tmp);		}	}	if(ans == 0)return ;	mark = 0;	for(int i=0;i 1){ans *= 2;return ;}			}		}	}	ans += (ans - 1);}void output() {	if(ans >= MAXN)puts("-1");	else cout<