搜索之BFS

发表于 更新于 分类于 阅读次数：

http://hihocoder.com/problemset/problem/1308
骑士巡游问题，简单来说就是关于在棋盘上放置若干个骑士，然后探究移动这些骑士是否能满足一定的而要求。举个例子啊：一个骑士从起始点开始，能否经过棋盘上所有的格子再回到起点。简单一点的比如棋盘上有3个骑士，能否通过若干次移动走到一起?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <string.h>

#define M 8
#define MAXN 1000
#define INF 0x8000000

typedef struct{
	int x,y;
}point;

point qu[MAXN];

int vis[3][M][M];
int move[8][2] = {{1,2}, {1,-2}, {-1,2}, {-1,-2}, {2,1}, {2,-1}, {-2,1}, {-2,-1}};

int check(int x, int y, int n){
    if( x>=0 && x <8 && y>=0 && y <8 && vis[n][x][y] == -1)
    	return 1;
    else
    	return 0;
}

void bfs_solve(int n, int x, int y){

     int i, head = 0, tail = -1;
     point tp;

     memset(vis[n], -1, sizeof(vis[n]));
     vis[n][x][y] = 0;
     tp.x = x;
     tp.y = y;
     qu[++tail] = tp;

     while(head <= tail){
     	int nowx, nowy;
        tp = qu[head++];
        nowx = tp.x;
        nowy = tp.y;

        for(i=0; i<8; ++i){
           int nx,ny;
           nx = nowx + move[i][0];
           ny = nowy + move[i][1];

           if(check(nx, ny, n)){
              vis[n][nx][ny] = vis[n][nowx][nowy] + 1;
              tp.x = nx;
              tp.y = ny;
              qu[++tail] = tp;
           }

        }
     }
}

void solve(int ch[][2]){
    int i,j;

    for(i=0; i<3; ++i){
       bfs_solve(i, ch[i][0], ch[i][1]);
    }

    int ans = INF;
    for(i=0; i<M; ++i)
    	for(j=0; j<M; ++j){
    	    int res = vis[0][i][j] + vis[1][i][j] + vis[2][i][j];
    	    if(ans > res)
    	    	ans = res;
    	}
    printf("%d\n", ans);
}


int main(){
    int i,j,T;
    int ch[3][2];

 	// FILE *fin = fopen("input.txt", "r");
    while(scanf("%d", &T) != EOF){

      for(j = 0; j<T; j++){
      	  char tmp[3];

	      for(i = 0; i < 3; ++i){
	          scanf("%s", &tmp);
	          ch[i][0] = tmp[0] - 'A';
	          ch[i][1] = tmp[1] - '1';
 	      }

	      solve(ch);
      }
    }
	return 0;
}