-
Notifications
You must be signed in to change notification settings - Fork 0
/
UVA_00439.cpp
64 lines (52 loc) · 1.53 KB
/
UVA_00439.cpp
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 <iostream>
#include <cstring>
#include <queue>
#define pr pair<int, int>
using namespace std;
int main(void)
{
int i, j, k, x, y, pos[2][2], cost[8][8];
string s[2];
bool visited[8][8];
queue <pr> q;
pr u;
int ind_x[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int ind_y[] = {-1, 1, -2, 2, -2, 2, -1, 1};
while(cin >> s[0] >> s[1])
{
pos[0][0] = s[0][0] - 'a';
pos[0][1] = s[0][1] - '1';
pos[1][0] = s[1][0] - 'a';
pos[1][1] = s[1][1] - '1';
for(i = 0; i < 8; i++)
for(j = 0; j < 8; j++)
visited[i][j] = false;
cout << "To get from " << s[0] << " to " << s[1] << " takes ";
q.push(make_pair(pos[0][0], pos[0][1]));
cost[pos[0][0]][pos[0][1]] = 0;
while(!q.empty())
{
u = q.front();
q.pop();
i = u.first;
j = u.second;
visited[i][j] = true;
if(i == pos[1][0] && j == pos[1][1])
break;
for(k = 0; k < 8; k++)
{
x = i + ind_x[k];
y = j + ind_y[k];
if(x >= 0 && y >=0 && x <= 7 && y <= 7 && !visited[x][y])
{
q.push(make_pair(x, y));
cost[x][y] = cost[i][j] + 1;
}
}
}
cout << cost[i][j] << " knight moves.\n";
while(!q.empty())
q.pop();
}
return 0;
}