CodeForces 374C 记忆化搜索

/*题目*/

题意：Inna喜欢Dima,所以他希望在一张n * m的 每个单元格印有‘D‘或者‘I‘或者‘M’或者‘A’ 的桌子上  尽量多的走出 某个路径 中包含DIMA 这个单词数量最多，必须从‘D‘开始走，并且‘D‘只能到‘I‘,然后‘I’只能到‘M‘,然后‘M’只能到‘A’，然后‘A‘只能到‘D‘，这样走，

若走不出DIMA这个单词 输出 poor dima

若存在环的话 输出 poor Inna

否则输出 走的路径中 包含 的最多的DIMA单词数量

他奶奶的 一开始，对于那个判断环的题意给弄错了，英文比较差，理解成了  若只存在一种数量的 DIMA就输出poor Inna,结果一直WA啊，搞了两个半小时，洗吧！

试了一把bfs超时，然后就考虑了记忆化搜索，dp[posx][posy] 代表以单元格(pos,posy)为起点 可以获得 多少个 DIMA单词，然后暴力枚举起点就可以了，中间操作 还要注意去判断环，还有各种回溯标记的问题

vector<pair<int,int >> G;

char mp[1000 + 55][1000 + 55];

int n,m;

int cnt;

int mark = 0;

int dir[4][2] = {-1,0,0,-1,1,0,0,1};

int dp[1000 + 55][1000 + 55];

bool flag[200][200];

bool vis[1000 + 55][1000 + 55];

void init() {
	G.clear();
	memset(vis,false,sizeof(vis));
	memset(flag,false,sizeof(flag));
	memset(dp,-1,sizeof(dp));
	flag['D' - 'A']['I' - 'A'] = true;
	flag['I' - 'A']['M' - 'A'] = true;
	flag['M' - 'A']['A' - 'A'] = true;
	flag['A' - 'A']['D' - 'A'] = true;
}

bool input() {
	while(cin>>n>>m) {
		for(int i=0;i<n;i++) {
			scanf("%s",mp[i]);
			for(int j=0;j<m;j++) {
				if(mp[i][j] == 'D')
					G.push_back(make_pair(i,j));
			}
		}
		return false;
	}
	return true;
}

int dfs(int posx,int posy,char ch) {
	if(dp[posx][posy] != -1)return dp[posx][posy];
	dp[posx][posy] = 0;
	if(mp[posx][posy] == 'A') {
		dp[posx][posy] = 1;
		cnt = 1;
	}
	int ret = 0;
	for(int i=0;i<4;i++) {
		int dx = posx + dir[i][0];
		int dy = posy + dir[i][1];
		if(!flag[ch - 'A'][mp[dx][dy] - 'A'])continue;
		if(dx < 0 || dx >= n || dy < 0 || dy >= m)continue;
		if(vis[dx][dy]){mark = 1;break;}
		vis[dx][dy] = true;
		int tmp = dfs(dx,dy,mp[dx][dy]);
		ret = max(ret,tmp);
		vis[dx][dy] = false;
	}
	return dp[posx][posy] += ret;
}

void cal() {
	int ans = 0;
	cnt = 0;
	mark = 0;
	for(int i=0;i<G.size();i++) {
		int u = G[i].first;
		int v = G[i].second;
		vis[u][v] = true;
		dfs(u,v,'D');
		int now = dp[u][v];
		ans = max(ans,now);
		vis[u][v] = false;
	}
	if(!cnt)puts("Poor Dima!");
	else if(mark)puts("Poor Inna!");
	else cout<<ans<<endl;
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}

CodeForces 374C 记忆化搜索

原文：http://blog.csdn.net/yitiaodacaidog/article/details/41558785