Inna and Dima

题意:从图上的任意一个D点按着DIMADIMA的顺序走,问一共可以经过多少个DIMA,如果经过0个DIMA就输出“Pool DIma!“,如果可以有无数多个DIMA就输出”Pool Inna!",否则就输出个数。

题解:DFS搜索就好了,这里我刚开的时候思考的是每次从不同的D点是给每个点标记都不同,然后会遇到从一个D点走的不同路并且不产生环的时候无法检查(菜死我了),后面发现如果产生环的时候,4个环的转弯点是方向是一定的,所以只要每次进行dfs的时候标记一下,从这个点退出的时候就把标记清空,这样如果遇到一个标记点就说明有环了。然后还有一个小bug找了半天,就是计数的时候提早一位计数了,没想到cf上只有一个点卡主了,最后自己测了好多次数据才反应过来。

 #include<bits/stdc++.h>
using namespace std;
char str[+][];
bool vis[+][+];
int cnt[+][+];
string DIMA = "DIMA";
int dx[] = {,-,,};
int dy[] = {,,,-};
bool endless = ;
void dfs(int x, int y, int n)
{
if(endless) return ;
n = (n+)%;
int num = ;
for(int i = ; i <= ; i++)
{
int x1 = x + dx[i];
int y1 = y + dy[i];
if(str[x1][y1] == DIMA[n]) //懒到不想判断边界,打死也不相信外面会有DIMA
{
if(vis[x1][y1])
{
endless = ;
return ;
}
else if(!cnt[x1][y1])
{
vis[x1][y1] = ;
dfs(x1,y1,n);
num = max(num, cnt[x1][y1]);
vis[x1][y1] = ;
}
else num = max(num, cnt[x1][y1]);
}
}
if(!cnt[x][y] &&n == ) num++; // 这里的n代表的是下一个”DIMA“的下标
cnt[x][y] = num; //当n变成0了之后其实就代表着这一位是A
return ;
}
int main()
{
int n, m;
scanf("%d%d",&n,&m);
memset(vis, , sizeof(vis));
memset(cnt, , sizeof(cnt));
memset(str, , sizeof(str));
for(int i = ; i <= n; i++)
scanf("%s", str[i]+);
int ans = ;
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
if(str[i][j] == 'D' && !cnt[i][j])
{
dfs(i, j, );
ans = max(ans,cnt[i][j]);
}
}
/*for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
printf("%d%c",cnt[i][j]," \n"[j==m]);*/
if(endless) printf("Poor Inna!\n");
else if(ans == ) printf("Poor Dima!\n");
else printf("%d", ans);
return ;
}
/*
5 5
DIMAD
DDDDI
DDDIM
DDDMA
DDDAD
*/
05-11 22:27