| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
二分匹配DFS算法 Brute Force#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator