Day6

Day6

今天学习的是 BFS + 存图方法

BFS:学起来很容易,但是DEBUG是真的累
由于自己比较笨,debug时间太长,没写完
知识点待补

OJ链接:https://vjudge.net/contest/313171#overview

BFS:广度优先搜索

链接:

存图方式

链式前向星

在了解什么是链式前向星之前,我们先来看一下什么是前向星。前向星其实就是一种边集数组。我们先把每条边的起点按照从小
到大的顺序排序如果起点一样,那么就按照终点从小到达来排序。并记录下以某个点为起点的所有边在数组中的起始位置和边
的数量,那么前向星就构造好了。

Rescue

Problem Description
Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel’s friends want to save Angel. Their task is: approach Angel. We assume that “approach Angel” is to get to the position where Angel stays. When there’s a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)
Input
First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. “.” stands for road, “a” stands for Angel, and “r” stands for each of Angel’s friend.

Process to the end of the file.
Output
For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing “Poor ANGEL has to stay in the prison all his life.”

1
2
3
4
5
6
7
8
9
10
11
Sample Input
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
Sample Output
13

code:

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
#include<bits/stdc++.h>
using namespace std;
char a[300][300];
int vis[300][300];
int n, m;

struct node{
int x, y;
int step;
friend bool operator < (node a, node b)
{
return a.step > b.step;
}
//重载运算符,用于自定义优先队列 的排序
};

int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void BFS(int x1, int y1, int x2, int y2)
{
memset(vis, 0, sizeof(vis));
//先将全部初始化,方便后面标记
priority_queue<node> q;
//优先队列
node e1, e2;
e1.x = x1, e1.y = y1, e1.step = 0;
q.push(e1);
vis[x1][y1] = 1;
int ans = -1;//表示不可能只走0步
while(!q.empty())
{
e1 = q.top();
q.pop();
if(e1.x == x2 && e1.y == y2)
{
ans = e1.step;
break;
}
for(int i = 0; i < 4; i ++)
{
e2.x = e1.x + d[i][0];
e2.y = e1.y + d[i][1];
//遍历寻找,如果不符合条件就continue
if(e2.x < 0 || e2.x >= n || e2.y < 0 || e2.y >= m || vis[e2.x][e2.y] == 1 || a[e2.x][e2.y] == '#')
continue;
else
{
if(a[e2.x][e2.y] == 'x') e2.step = e1.step + 2;
else e2.step = e1.step + 1;
}
//遍历完一定要把新的数加入队列!!
q.push(e2);
vis[e2.x][e2.y] = 1;
}
}
if(ans == -1) puts("Poor ANGEL has to stay in the prison all his life.");
else cout << ans << endl;
}



int main()
{
int x1, y1, x2, y2;
while(~scanf("%d %d",&n,&m))
{
for(int i = 0; i < n; i ++)
{
scanf("%s",&a[i]);
}
//双重for循环来寻找开始的点和 结束的点
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
if(a[i][j] == 'a')
{
x1 = i;
y1 = j;
}
if(a[i][j] == 'r')
{
x2 = i;
y2 = j;
}
}
}
BFS(x1, y1, x2, y2);
}
return 0;
}

Red and Black

Problem Description
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

‘.’ - a black tile
‘#’ - a red tile
‘@’ - a man on a black tile(appears exactly once in a data set)
Output
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

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
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
Sample Output
45
59
6
13

code:

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<bits/stdc++.h>
using namespace std;
const int mod = 300;
int n, m; //n表示行 ,m表示列
char a[mod][mod];
int vis[mod][mod];
int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

//struct node{
// int x, y;
// int step;
//用优先队列的时候加上friend bool operator
// friend bool operator < (node a, node b)
// {
// return a.step > b.step;
// }
//};
//优先队列的BFS
//void BFS(int x1, int y1)
//{
// memset(vis, 0, sizeof(vis));
//
// priority_queue<node> q;
// node e1, e2;
// e1.x = x1, e1.y = y1;
// q.push(e1);
// vis[e1.x][e1.y] = 1;
// int num = 1;
// while(!q.empty())
// {
// e1 = q.top();
// q.pop();
// for(int i = 0; i < 4; i ++)
// {
// e2.x = e1.x + d[i][0];
// e2.y = e1.y + d[i][1];
// if(e2.x < 0 || e2.x >= n || e2.y < 0 || e2.y >= m || vis[e2.x][e2.y] == 1 || a[e2.x][e2.y] == '#') continue;
// else num ++; //e2.step = e1.step + 1;
// q.push(e2);
// vis[e2.x][e2.y] = 1;
// }
// }
// cout << num << endl;
//}
//
//


//不是优先队列的BFS
//struct node{
// int x, y;
// int step;
//};
//void BFS(int x1, int y1)
//{
// memset(vis, 0, sizeof(vis));
//
// queue<node> q;
// node e1, e2;
// e1.x = x1, e1.y = y1;
// q.push(e1);
// vis[e1.x][e1.y] = 1;
// int num = 1;
// while(!q.empty())
// {
// e1 = q.top();
// q.pop();
// for(int i = 0; i < 4; i ++)
// {
// e2.x = e1.x + d[i][0];
// e2.y = e1.y + d[i][1];
// if(e2.x < 0 || e2.x >= n || e2.y < 0 || e2.y >= m || vis[e2.x][e2.y] == 1 || a[e2.x][e2.y] == '#') continue;
// else num ++;
// q.push(e2);
// vis[e2.x][e2.y] = 1;
// }
// }
// cout << num << endl;
//}


//int main()
//{
//
// int x1, y1, x2, y2;
// while(~scanf("%d %d",&m,&n))
// {
// if(n == 0 && m == 0) break;
// for(int i = 0; i < n; i ++)
// {
// scanf("%s",&a[i]);
// }
// for(int i = 0; i < n; i ++)
// {
// for(int j = 0; j < m; j ++)
// {
// if(a[i][j] == '@')
// {
// x1 = i;
// y1 = j;
// }
// }
// }
// BFS(x1, y1);
// }
//
// return 0;
//}



//DFS
int num;
void DFS(int x1, int y1)
{
int xx, yy;
a[x1][y1] = '#';
num ++;

for(int i = 0; i < 4; i ++)
{
xx = x1 + d[i][0];
yy = y1 + d[i][1];
if(xx < 0 || xx >= n || yy < 0 || yy >= m || a[xx][yy] == '#') continue;
else DFS(xx, yy);
}
}

int main()
{
int x1, y1;
while(~scanf("%d %d",&m,&n))
{
if(n == 0 && m == 0) break;
for(int i = 0; i < n; i ++)
{
scanf("%s", &a[i]);
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
if(a[i][j] == '@')
{
x1 = i;
y1 = j;
}
}
}
memset(vis, 0, sizeof(vis));
num = 0;
DFS(x1, y1);
cout << num << endl;
}

return 0;
}

Battle City

Problem Description
Many of us had played the game “Battle city” in our childhood, and some people (like me) even often play it on computer now.

What we are discussing is a simple edition of this game. Given a map that consists of empty spaces, rivers, steel walls and brick walls only. Your task is to get a bonus as soon as possible suppose that no enemies will disturb you (See the following picture).

Your tank can’t move through rivers or walls, but it can destroy brick walls by shooting. A brick wall will be turned into empty spaces when you hit it, however, if your shot hit a steel wall, there will be no damage to the wall. In each of your turns, you can choose to move to a neighboring (4 directions, not 8) empty space, or shoot in one of the four directions without a move. The shot will go ahead in that direction, until it go out of the map or hit a wall. If the shot hits a brick wall, the wall will disappear (i.e., in this turn). Well, given the description of a map, the positions of your tank and the target, how many turns will you take at least to arrive there?
Input
The input consists of several test cases. The first line of each test case contains two integers M and N (2 <= M, N <= 300). Each of the following M lines contains N uppercase letters, each of which is one of ‘Y’ (you), ‘T’ (target), ‘S’ (steel wall), ‘B’ (brick wall), ‘R’ (river) and ‘E’ (empty space). Both ‘Y’ and ‘T’ appear only once. A test case of M = N = 0 indicates the end of input, and should not be processed.
Output
For each test case, please output the turns you take at least in a separate line. If you can’t arrive at the target, output “-1” instead.

1
2
3
4
5
6
7
8
Sample Input
3 4
YBEB
EERE
SSTE
0 0
Sample Output
8

code:

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
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod = 350;
const int INF = 5;

char a[mod][mod];
int vis[mod][mod];
int n, k;

struct node{
int x, y;
int step;
friend bool operator < (node a, node b)
{
return a.step > b.step;
}
};

int d[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
void BFS(int x1, int y1, int x2, int y2)
{
memset(vis, 0, sizeof(vis));
priority_queue<node> q;
node e1, e2;
e1.x = x1, e1.y = y1, e1.step = 0;
q.push(e1);
vis[x1][y1] = 1;
int ans = -1;
while(!q.empty())
{
e1 = q.top();
q.pop();
if(e1.x == x2 && e1.y == y2)
{
ans = e1.step;
break;
}
for(int i = 0; i < 4; i ++)
{
e2.x = e1.x + d[i][0];
e2.y = e1.y + d[i][1];
if(e2.x < 0 || e2.x >= n || e2.y < 0 || e2.y >= k || vis[e2.x][e2.y] == 1) continue;
else
{
if(a[e2.x][e2.y] == 'S' || a[e2.x][e2.y] == 'R') continue;
if(a[e2.x][e2.y] == 'B') e2.step = e1.step + 2;
else e2.step = e1.step + 1;
}
q.push(e2);
vis[e2.x][e2.y] = 1;
}
}
if(ans == -1) puts("-1");
else cout << ans << endl;
}

int main()
{
int x1, x2, y1, y2;
while(~scanf("%d %d",&n, &k))
{
if(n == 0 && k == 0) break;
for(int i = 0; i < n; i ++)
{
scanf("%s",&a[i]);
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < k; j ++)
{
if(a[i][j] == 'Y')
{
x1 = i;
y1 = j;
}
if(a[i][j] == 'T')
{
x2 = i;
y2 = j;
}
}
}
BFS(x1, y1, x2, y2);
}

return 0;
}

Catch That Cow

Problem Description
农夫知道一头牛的位置,想要抓住它。农夫和牛都于数轴上 ,农夫起始位于点 N(0<=N<=100000) ,牛位于点 K(0<=K<=100000) 。农夫有两种移动方式: 1、从 X移动到 X-1或X+1 ,每次移动花费一分钟 2、从 X移动到 2*X ,每次移动花费一分钟 假设牛没有意识到农夫的行动,站在原地不。最少要花多少时间才能抓住牛?
Input
一行: 以空格分隔的两个字母: N 和 K
Output
一行: 农夫抓住牛需要的最少时间,单位分钟

1
2
3
4
5
6
Sample Input
5 17
Sample Output
4
Hint
农夫使用最短时间抓住牛的方案如下: 5-10-9-18-17, 需要4分钟.

code:

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
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod = 1e5 + 10;

int vis[mod];
int n, k;

struct node{
int x;
int step;
friend bool operator < (node a, node b)
{
return a.step > b.step;
}
};

void BFS(int x1, int x2)
{
memset(vis, 0, sizeof(vis));
priority_queue<node> q;
node e1, e2;
e1.x = x1, e1.step = 0;

vis[e1.x] = 1;
q.push(e1);
while(!q.empty())
{
e1 = q.top();
q.pop();
if(e1.x == x2) break;
else
{
if(e1.x - 1 > 0 && vis[e1.x - 1] == 0)
{
e2.x = e1.x - 1;
e2.step = e1.step + 1;
vis[e2.x] = 1;
q.push(e2);
}
if(e1.x + 1 <= 100000 && vis[e1.x + 1] == 0)
{
e2.x = e1.x + 1;
e2.step = e1.step + 1;
vis[e2.x] = 1;
q.push(e2);
}
if(e1.x * 2 <= 100000 && vis[e1.x * 2] == 0)
{
e2.x = e1.x * 2;
e2.step = e1.step + 1;
vis[e2.x] = 1;
q.push(e2);
}
}
}
cout << e1.step << endl;
}

int main()
{
while(~scanf("%d %d",&n, &k))
{
if(n > k) cout << n - k << endl;
else BFS(n, k);

}

return 0;
}

Dungeon Master

Problem Description
你被困在一个三维的空间中,现在要寻找最短路径逃生!
空间由立方体单位构成
你每次向上下前后左右移动一个单位需要一分钟
你不能对角线移动并且四周封闭
是否存在逃出生天的可能性?如果存在,则需要多少时间?
Input - 输入
输入第一行是一个数表示空间的数量。
每个空间的描述的第一行为L,R和C(皆不超过30)。
L表示空间的高度。
R和C分别表示每层空间的行与列的大小。
随后L层地牢,每层R行,每行C个字符。
每个字符表示空间的一个单元。’#’表示不可通过单元,’.’表示空白单元。你的起始位置在’S’,出口为’E’。
每层空间后都有一个空行。L,R和C均为0时输入结束。
Output - 输出
每个空间对应一行输出。
如果可以逃生,则输出如下
Escaped in x minute(s).
x为最短脱离时间。
如果无法逃生,则输出如下
Trapped!

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
Sample Input - 输入样例
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
Sample Output - 输出样例
Escaped in 11 minute(s).
Trapped!

code:

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int mod = 30;

int L, R, C;
char a[mod][mod][mod];
int vis[mod][mod][mod];

struct node{
int x, y, z;
int t;
friend bool operator < (node a, node b)
{
return a.t > b.t;
}
}s, e, e1;
//判断是否到达终点
bool yes(node sss)
{
if(sss.x == e.x && sss.y == e.y && sss.z == e.z)
return true;
else
return false;
}

// 判断该点是否越界
bool check(int x, int y, int z)
{
if(x >= 0 && x < L && y >= 0 && y < R && z >= 0 && z < C && !vis[x][y][z] && (a[x][y][z] == '.' || a[x][y][z] == 'E'))
return true;
else
return false;
}
int d[6][3] = {
1, 0, 0,
-1, 0, 0,
0, 1, 0,
0, -1, 0,
0, 0, 1,
0, 0, -1
};
int ans;
void BFS()
{
memset(vis, 0, sizeof(vis));
priority_queue<node> q;
node e2;
e1.x = s.x, e1.y = s.y, e1.z = s.z, e1.t = 0;
q.push(e1);
vis[e1.x][e1.y][e1.z] = 1;
while(!q.empty())
{
e1 = q.top();
q.pop();
if(yes(e1))
{
ans = e1.t;
break;
}
else
{
for(int i = 0; i < 6; i ++)
{
e2.x = e1.x + d[i][0];
e2.y = e1.y + d[i][1];
e2.z = e1.z + d[i][2];
if(check(e2.x, e2.y, e2.z))
{
e2.t = e1.t + 1;
q.push(e2);
vis[e2.x][e2.y][e2.z] = 1;
}
else continue;
}
}
}

}

int main()
{
while(~scanf("%d %d %d",&L, &R, &C))
{
if(L == 0 && R == 0 && C == 0) break;
for(int i = 0; i < L; i ++)
{
for(int j = 0; j < R; j ++)
{
for(int k = 0; k < C; k ++)
{
cin >> a[i][j][k];
}
}
}
for(int i = 0; i < L; i ++)
{
for(int j = 0; j < R; j ++)
{
for(int k = 0; k < C; k ++)
{
if(a[i][j][k] == 'S')
{
s.x = i;
s.y = j;
s.z = k;
}
if(a[i][j][k] == 'E')
{
e.x = i;
e.y = j;
e.z = k;
}
}
}
}
BFS();
if(e1.x == e.x && e1.y == e.y && e1.z == e.z)
printf("Escaped in %d minute(s).\n", ans);
else
printf("Trapped!\n");
}

return 0;
}

Robot Motion

Problem Description

A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are

N north (up the page)
S south (down the page)
E east (to the right on the page)
W west (to the left on the page)

For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid.

Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop through 8 instructions, and never exits.

You are to write a program that determines how long it takes a robot to get out of the grid or how the robot loops around.
Input
There will be one or more grids for robots to navigate. The data for each is in the following form. On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in the grid, and the number of the column in which the robot enters from the north. The possible entry columns are numbered starting with one at the left. Then come the rows of the direction instructions. Each grid will have at least one and at most 10 rows and columns of instructions. The lines of instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a row containing 0 0 0.
Output
For each grid in the input there is one line of output. Either the robot follows a certain number of instructions and exits the grid on any one the four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions on some number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word “step” is always immediately followed by “(s)” whether or not the number before it is 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Sample Input
3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0
Sample Output
10 step(s) to exit
3 step(s) before a loop of 8 step(s)

code:

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[12][12];
int vis[12][12];
int main()
{
int a,b,c;
while(scanf("%d %d %d",&a,&b,&c))
{
if(a==0&&b==0&&c==0) break;
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
cin>>s[i][j];
int x=0,y=c-1,step=0;
memset(vis,0,sizeof(vis));
while(true)
{
step++;
if(s[x][y]=='N'&&!vis[x][y])
{
vis[x][y]=step;
x--;
}
else if(s[x][y]=='S'&&!vis[x][y])
{
vis[x][y]=step;
x++;
}
else if(s[x][y]=='W'&&!vis[x][y])
{
vis[x][y]=step;
y--;
}
else if(s[x][y]=='E'&&!vis[x][y])
{
vis[x][y]=step;
y++;
}
if(x<0||x==a||y<0||y==b)
{
printf("%d step(s) to exit\n",step); break;
}
else if(vis[x][y])
{
printf("%d step(s) before a loop of %d step(s)\n",vis[x][y]-1,step+1-vis[x][y]);
break;
}
}
}
}

Number Transformation

Problem Description
In this problem, you are given an integer number s. You can transform any integer number A to another integer number B by adding x to A. This x is an integer number which is a prime factor of A (please note that 1 and A are not being considered as a factor of A). Now, your task is to find the minimum number of transformations required to transform s to another integer number t.
Input
Input starts with an integer T (≤ 500), denoting the number of test cases.
Each case contains two integers: s (1 ≤ s ≤ 100) and t (1 ≤ t ≤ 1000).
Output
For each case, print the case number and the minimum number of transformations needed. If it’s impossible, then print -1.

1
2
3
4
5
6
7
Sample Input
2
6 12
6 13
Sample Output
Case 1: 2
Case 2: -1

code:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f

const int maxx = 1e5;

struct node{
int x, step;
friend bool operator < (node a, node b)
{
return a.step > b.step;
}
};

bool vis[10010];
int p[10010];
int s, t, k, ans;

void prime(int n)
{
k = 0;
int m;
m = n;
for(int i = 2; i <= sqrt(n); i ++)
{
if(n % i == 0)
{
p[++ k] = i;
while(n % i == 0) n /= i;
}
}
if(n > 1 && m != n) p[++ k] = n;
}

void BFS()
{
priority_queue<node> q;
node e1, e2;
e1.x = s, e1.step = 0;
vis[s] = 1;
q.push(e1);
bool flag = 0;
while(!q.empty())
{
e1 = q.top();
q.pop();
if(e1.x == t)
{
flag = 1;
ans = min(ans, e1.step);
continue;
}
memset(p, 0, sizeof(p));
prime(e1.x);
for(int i = 1; i <= k; i ++)
{
e2.x = e1.x + p[i];
e2.step = e1.step + 1;
if(e2.x <= t && !vis[e2.x])
{
vis[e2.x] = 1;
q.push(e2);
}
}
}
if(flag) cout << ans << endl;
else puts("-1");
}

int main()
{
int n, kase = 0;
cin >> n;
while(n --)
{
ans = INF;
memset(vis, 0, sizeof(vis));
cin >> s >> t;
printf("Case %d: ", ++ kase);
if(s == t)
{
puts("0");
continue;
}
if(s > t)
{
puts("-1");
continue;
}
BFS();
}
return 0;
}

Knight Moves

Problem Description
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the “difficult” part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input
The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output
For each test case, print one line saying “To get from xx to yy takes n knight moves.”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Sample Input
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

code:

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
#include<bits/stdc++.h>
using namespace std;
#define max_v 30
int vis[max_v][max_v];
int dir[8][2]= {1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2};
int ans;
int sx, sy, fx, fy;
struct node
{
int x,y,step;
};
void BFS()
{
memset(vis, 0, sizeof(vis));
queue<node> q;
node e1, e2;
e1.x = sx;
e1.y = sy;
e1.step = 0;
vis[e1.x][e1.y] = 1;
q.push(e1);

while(!q.empty())
{
e1 = q.front();
q.pop();

if(e1.x == fx && e1.y == fy)
{
ans = e1.step;
return ;
}

for(int i = 0; i < 8; i ++)
{
e2.x = e1.x + dir[i][0];
e2.y = e1.y + dir[i][1];

if(e2.x >= 1 && e2.y >= 1 && e2.x <= 8 && e2.y <= 8 && vis[e2.x][e2.y] == 0)
{
e2.step = e1.step + 1;
vis[e2.x][e2.y] = 1;
q.push(e2);
}
}
}
}
int main()
{
char x1, x2;
int y1, y2;

while(~scanf("%c%d %c%d",&x1,&y1,&x2,&y2))
{
getchar();
sx=x1-'a'+1;
sy=y1;
fx=x2-'a'+1;
fy=y2;
BFS();
printf("To get from %c%d to %c%d takes %d knight moves.\n",x1, y1, x2, y2, ans);
}
return 0;
}

---------------- The End ----------------
0%