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