程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 358E - Dima and Kicks

CodeForces 358E - Dima and Kicks

編輯：C++入門知識

CodeForces 358E - Dima and Kicks

dfs判斷歐拉圖，紅名選手的代碼就是炫酷。

首先統計所有點的度數總和，而後對於這張圖的特殊性——每個點最多只會有四條邊，來標記當前邊是否走過了。

若在一次DFS中，能遍歷所有的節點則輸出所有邊長的gcd的大於1的約數集。

真心學習了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned __int64
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 20090717

using namespace std;

bool vis[1002][1002][4];

int num[1010][1010];

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

int total;

int ans;

void dfs(int x,int y,int d,int len)
{
    bool mark = false;
    for(int i = 0;i < 4; ++i)
    {
        if(0 == num[x+dir[0][i]][y+dir[1][i]] || vis[x][y][i] == true)
            continue;
        vis[x][y][i] = true,vis[x+dir[0][i]][y+dir[1][i]][(i+2)%4] = true;

        total -= 2;

        if(d != -1 && i != d)
            ans = __gcd(ans,len),dfs(x+dir[0][i],y+dir[1][i],i,1);
        else
            dfs(x+dir[0][i],y+dir[1][i],i,len+1);
         mark = true;
    }

    if(mark == false)
        ans = __gcd(ans,len);
}

int main()
{
    int n,m,i,j,k;

    scanf("%d %d",&n,&m);

    memset(num,0,sizeof(num));

    for(i = 1;i <= n; ++i)
        for(j = 1;j <= m; ++j)
            scanf("%d",&num[i][j]);

    int odd = 0;

    ans = 0;
    total = 0;

    for(i = 1;i <= n; ++i)
        for(j = 1;j <= m; ++j)
        {
            if(num[i][j] == 0)
                continue;
            for(ans = 0,k = 0;k < 4; ++k)
                ans += num[i+dir[0][k]][j+dir[1][k]];
            total += ans;
            if(ans == 0)
                return puts("-1"),0;
            if(ans&1)
                odd++;
        }

    if(odd != 0 && odd != 2)
        return puts("-1"),0;

    memset(vis,false,sizeof(vis));

    ans = 0;

    for(i = 1;i <= n; ++i)
        for(j = 1;j <= m; ++j)
            if(num[i][j])
            {
                dfs(i,j,-1,0);
                goto V;
            }
    V:;

    if(total || ans <= 1)
        return puts("-1"),0;

    for(i = 2;i < ans; ++i)
        if(ans%i == 0)
            printf("%d ",i);
    printf("%d\n",ans);
    return 0;
}