CodeForces 382D Ksenia and Pawns __DFS

题意：给出一个棋盘和两个棋子，‘#‘可以同时放两个棋子，其他的最多只能放一个。开始时在棋盘上放两个棋子，每一回合两个棋子必须移动且只能按照指示方向移动一个格子。一个棋子移动一步就获得一分，问最后能获得多少分。

思路：对于每一个格子，只能走向一个格子，但是可能能从多个格子走过来。则逆向建图就再合适不过了。因为在没有环的情况下，逆向建图每个节点的入度 <= 1,出度<=4,

显然此时可以得到一个森林，也可能只有一棵树。则问题转化成在森林中找深度最深的树。

设最大深度为MaxDepth,若深度为MaxDepth的树有两棵，则最大得分MaxScore = MaxDepth * 2 -2;

若只有一棵，则有两种情况，当根节点有多棵子树，且这些子树中有两棵及以上达到了最大深度，则答案仍为MaxScore = MaxDepth * 2 -2;

否则有MaxScore = MaxDepth * 2 -2-1;减 1 是因为两个棋子要错开一个格子。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>

#define LL long long
#define PI (acos(-1.0))
#define EPS (1e-10)

using namespace std;

char Map[2010][2010];

const int MAXN = 2000*2000+10;

int Top_Edge = -1;

struct N
{
    int v,next;
}Edge[MAXN];

int head[MAXN];

void link(int u,int v)
{
    Edge[++Top_Edge].v = v;
    Edge[Top_Edge].next = head[u];
    head[u] = Top_Edge;
}

bool id[MAXN],od[MAXN],mv[MAXN];

int Ans = 0,MaxDepth = -1;

int dfs(int s,int h)
{
    mv[s] = true;

    int TD,MD = 1,ans = 0;

    for(int p = head[s]; p != -1; p = Edge[p].next)
    {
        if(mv[Edge[p].v] == false)
        {
            TD = dfs(Edge[p].v,h+1);
            if(TD+1 > MD)
            {
                MD = TD+1;
                ans = 1;
            }
            else if(TD+1 == MD)
            {
                ans++;
            }
        }
        else
        {
            return -1;
        }
    }

    if(h == 1)
    {
        while(ans--)
        {
            if(MD > MaxDepth)
            {
                MaxDepth = MD;
                Ans = 1;
            }
            else if(MD == MaxDepth)
            {
                Ans++;
            }
        }
    }

    return MD;
}

int main()
{
    int top,n,m,i,j,ans = 0;
    scanf("%d %d",&n,&m);
    for(i = 1;i <= n; ++i)
    {
        scanf("%s",Map[i]+1);
    }

    top = n*m;

    memset(id,false,sizeof(bool)*(top+2));
    memset(od,false,sizeof(bool)*(top+2));
    memset(mv,false,sizeof(bool)*(top+2));
    memset(head,-1,sizeof(int)*(top+2));

    for(i = 1;i <= n; ++i)
    {
        for(j = 1;j <= m; ++j)
        {
            if(Map[i][j] == ‘>‘)
            {
                ans++;
                link((i-1)*m+j+1,(i-1)*m+j);
                od[(i-1)*m+j+1] = true;
                id[(i-1)*m+j] = true;
            }
            else if(Map[i][j] == ‘<‘)
            {
                ans++;
                link((i-1)*m+j-1,(i-1)*m+j);
                od[(i-1)*m+j-1] = true;
                id[(i-1)*m+j] = true;
            }
            else if(Map[i][j] == ‘^‘)
            {
                ans++;
                link((i-2)*m+j,(i-1)*m+j);
                od[(i-2)*m+j] = true;
                id[(i-1)*m+j] = true;
            }
            else if(Map[i][j] == ‘v‘)
            {
                ans++;
                link(i*m+j,(i-1)*m+j);
                od[i*m+j] = true;
                id[(i-1)*m+j] = true;
            }
        }
    }

    for(i = 1;i <= top; ++i)
    {
        if(od[i] && id[i] == false)
        {
            //cout<<i<<endl;
            dfs(i,1);
            ans++;
        }
    }

    for(i = 1;i <= top; ++i)
    {
        if(mv[i])
            ans--;
    }

    if(ans != 0)
    {
        printf("-1\n");
    }
    else
    {
        if(Ans >= 2)
        {
            printf("%d\n",MaxDepth*2-2);
        }
        else if(Ans == 0)
        {
            printf("%d\n",0);
        }
        else
        {
            printf("%d\n",MaxDepth*2-3);
        }
    }

    return 0;
}

CodeForces 382D Ksenia and Pawns __DFS

原文：http://blog.csdn.net/zmx354/article/details/18497511