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
  
   > 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 || 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