CodeforcesRound#224(Div.2)D暴力搜索加記憶化_html/css

題意讀了半年，英語太渣，題意是擺兩個(gè)棋子在棋盤上作為起點(diǎn)，但是起點(diǎn)不能在#上，然后按照?qǐng)D的指示開始走， < 左 > 右 ^上 v下，走的時(shí)候只能按照?qǐng)D的指示走，如果前方是 #的話，可以走進(jìn)去，但是 走進(jìn)去之后便不能再走了，走的途中兩個(gè)棋子不能相碰，但是最終都走到同一個(gè)#里是沒事的，并且若是能走 無限步的話 輸出 -1， 例如 > < 這樣左右左右的走就能無限走，然后問你 兩個(gè)棋子走的最大步數(shù)的和

一開始被輸出-1給困住了，因?yàn)槌?.> <這樣以外 還可以剛好形成一個(gè)圈，這樣不太好判，而且不太敢寫dfs因?yàn)?圖是 2000 * 2000的有點(diǎn)大，反向的DFS也沒想到，沒法子也只能記憶化搜索一下，設(shè)dis[i][j]代表 由 (i,j)作為 起點(diǎn)能走的最遠(yuǎn)步數(shù)，這樣覺得時(shí)間上應(yīng)該能過去，然后枚舉每一個(gè)點(diǎn)作為起點(diǎn) 進(jìn)行深搜，這里就能判斷是否為-1的情況，因?yàn)閳D為 2000 * 2000的，所以最多讓你走 4000000步數(shù)，兩個(gè)棋子一前一后跟著走的話 那么最多不會(huì)超過8000000，所以可以設(shè)置一個(gè)最大值MAXN = 8000000,一旦 重新走了標(biāo)記過的也就是路過的點(diǎn) 就返回這個(gè)值，就能判定是否為-1，

求出每個(gè)點(diǎn)作為起點(diǎn)的最大步數(shù)以后，開始尋找，若有兩個(gè)點(diǎn)的最大步數(shù)相同，而且他們?cè)谧叩倪^程中沒有相碰，這樣最大步數(shù)和 就是 ans + ans ，若找不到的話 一前一后放置兩個(gè)棋子肯定就是最優(yōu)得了 也就是 ans + ans - 1，好了就是代碼的 實(shí)現(xiàn)了，深搜寫的有點(diǎn)搓，

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< 




聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com