Description
Mr. B has recently discovered the grid named "spiral grid".
Construct the grid like the following figure. (The grid is actually infinite. The figure is only a small part of it.)
Considering traveling in it, you are free to any cell containing a composite number or 1, but traveling to any cell containing a prime number is disallowed. You can travel up, down, left or right, but not diagonally. Write a program to find the length of the shortest path between pairs of nonprime numbers, or report it's impossible.
Input
Each test case is described by a line of input containing two nonprime integer 1 <=x, y<=10,000.
Output
For each test case, display its case number followed by the length of the shortest path or "impossible" (without quotes) in one line.
Sample Input
复制代码1
2
31 4 9 32 10 12
Sample Output
复制代码1
2
3Case 1: 1 Case 2: 7 Case 3: impossible
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111#include <stdio.h> #include <string.h> #include <queue> using namespace std; const int MAX = 210; // 方格边长 int MAX2 = MAX*MAX; int a[MAX+2][MAX+2]; bool isPrime[MAX*MAX+5]; bool vd[MAX+2][MAX+2]; //构造方格 void createGrid(){ int num = MAX * MAX; int top = 1, bottom = MAX, left = 1, right = MAX; int x = 1, y = 1; // 左上角(1, 1)是起始点 while (num >= 1){ for ( ; y <= right; y++) // 向右 a[x][y] = num--; top++; for (x++,y--; x <= bottom; x++) // 向下 a[x][y] = num--; right--; for (x--,y--; y >= left; y--) // 向左 a[x][y] = num--; bottom--; for (x--,y++; x >= top; x--) // 向上 a[x][y] = num--; x++,y++; left++; } } // 构造素数表 void getPrime(){ memset(isPrime, 1, sizeof(isPrime)); isPrime[1] = false; for (int i = 2; i <= MAX2; i++){ if (isPrime[i]){ for (int j = i+i; j <= MAX2; j+=i) isPrime[j] = false; } } } //获取元素坐标 void getLocate(int v, int &x, int &y){ for (int i = 1; i <= MAX; i++) for (int j = 1; j <= MAX; j++) if (a[i][j] == v){ x = i; y = j; return ; } } typedef struct{ int x, y, step; }node; // 方向:上、左、下、右 int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}}; int bfs(int v, int u){ if (v == u) return 0; queue<node> q; int vx, vy; node tmp, now; memset(vd, 0, sizeof(vd)); getLocate(v, vx, vy); tmp.x = vx, tmp.y = vy, tmp.step = 0; vd[vx][vy] = true; q.push(tmp); while (!q.empty()){ tmp = q.front(); q.pop(); for (int i = 0; i < 4; i++){ now.x = tmp.x + dir[i][0]; now.y = tmp.y + dir[i][1]; now.step = tmp.step + 1; if (now.x<1 || now.x>MAX || now.y<1 || now.y>MAX || isPrime[a[now.x][now.y]]) continue; if (a[now.x][now.y] == u) return now.step; if (!vd[now.x][now.y]){ vd[now.x][now.y] = true; q.push(now); } } } return -1; } int main() { createGrid(); getPrime(); int u, v; int t = 1; int ans; while (~scanf("%d %d", &v, &u)){ ans = bfs(v, u); if (ans == -1) printf("Case %d: impossiblen", t++); else printf("Case %d: %dn", t++, ans); } return 0; }
最后
以上就是孤独红酒最近收集整理的关于HDU - 4255 A Famous Grid 【BFS】的全部内容,更多相关HDU内容请搜索靠谱客的其他文章。
发表评论 取消回复