Codeforces 374 C Inna and Dima (DFS)

题意：从图上的任意一个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

 */

巴特西

Codeforces 374 C Inna and Dima (DFS)

最新文章

热门文章