Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

二分匹配DFS算法 Brute Force

Posted by Dir at 2010-04-20 20:28:09 on Problem 2495
#include <stdio.h>
#include <memory.h>

int pre[10][10];
int visited[10][10];

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int a,b,c,d;
int DFS(int di, int dj)
{
    int i,ii,jj;
    visited[di][dj] = 1;
    for (i = 0; i < 4; i ++)
    {
        ii = di + dx[i];
        jj = dj + dy[i];
        if (ii >= 1 && ii <= 8 && jj >= 1 && jj <= 8 && !visited[ii][jj])
        {
            if (!((ii == a && jj == b) || (ii == c && jj == d)))
            {
                visited[ii][jj] = 1;
                if (pre[ii][jj] == -1 || DFS((pre[ii][jj] - 1) / 8 + 1, (pre[ii][jj] - 1) % 8 + 1))
                {
                    pre[ii][jj] = (di - 1) * 8 + dj;
                    pre[di][dj] = (ii - 1) * 8 + jj;
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    int cc,tt,sum;
    int i,j;
    scanf("%d",&tt);
    for (cc = 1; cc <= tt; cc ++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        memset(pre,-1,sizeof(pre));
        sum = 0;
        for (i = 1; i <= 8; i ++)
        {
            for (j = 1; j <= 8; j ++)
            {
                if (!((i == a && j == b) || (i == c && j == d)) && pre[i][j] == -1)
                {
                    memset(visited,0,sizeof(visited));
                    if (DFS(i,j))
                    {
                        sum ++;
                    }
                }
            }
        }
        
        printf("Scenario #%d:\n",cc);
        printf("%d\n\n",sum == 31);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator