1064. The way a Knight
On a chessboard consisting
of n×n cells, several of them are cut. Find the path of minimum length
for a Knight from one cell to another. The Knight can’t go through cut cells.
Input. The first row is set to the number n (2 ≤ n ≤
50). Each of the next n lines
contains n symbols. The symbol #
denotes the cut cell, the point is not a cut cell, and the symbol @ denotes the
initial and final cell of the Knight’s path (the chessboard contains two such
characters).
Output. If the path can not be constructed, print “Impossible”.
Otherwise, print the same map as the input, but check all Knight intermediate
positions with the symbol @.
|
Sample
input |
Sample
output |
5@..@...##...........
..... |
@..@. ..##. .@..@ ..@.. @.... |
graphs – breadth first search
To solve the
problem, it is enough to run a breadth-first search from one of the cells,
denoted by the @ symbol. Then, using the array of ancestors, restore the
shortest path, if it exists.
Algorithm realization
In the arrays dx
and dy we describe all possible moves of the knight. From the cell (i, j) the knight can go to one of the cells (i
+ dx[k], j + dy[k]), 0 ≤ k ≤ 7.
int dx[] = {1,1,-1,-1,2,2,-2,-2};
int dy[] = {2,-2,2,-2,1,-1,1,-1};
Store the
position of the knight on the board as a pair of coordinates (x,
y). For this we declare
the CELL structure. Let's declare cell comparison operators (“equal to” and
“not equal to”).
struct CELL
{
int x, y;
CELL(int a =
-1, int b = -1) : x(a), y(b) {};
};
int operator==(CELL
a, CELL b)
{
return (a.x
== b.x) && (a.y == b.y);
}
int operator!=(CELL
a, CELL b)
{
return !((a.x
== b.x) && (a.y == b.y));
}
Let’s declare an
array of ancestors Parent. An ancestor array will be used to remember the visited cells of
the chessboard. If Parent[i][j] = (-1, -1), then cell (i,
j) has not yet been visited by the horse. Let’s define an
empty cell EMPTY_CELL.
CELL
EMPTY_CELL(-1,-1), Start(-1,-1), Finish(-1,-1);
CELL Parent[MAX][MAX];
The initial
state of the board we read into the array s.
char s[MAX][MAX];
The function CanGo returns 1 if cell c is not outside the field
boundary.
int CanGo(CELL c)
{
return !((c.x
< 0) || (c.x >= n) || (c.y < 0) || (c.y >= n));
}
The function bfs runs the breadth first search from the cell Start. Let’s declare the queue d.
void bfs(CELL Start)
{
deque<CELL> d;
d.push_back(Start);
s[Start.x][Start.y] = '#';
while(!d.empty())
{
Take the position of type Node from the head of the queue. Make all possible moves with the knight from there.
CELL Node = d.front(); d.pop_front();
for(int k = 0; k < 8; k++)
{
CELL Next = CELL(Node.x + dx[k], Node.y +
dy[k]);
If the move is made to position Next,
which is located outside the edges of the board, then it is impossible to make
it.
if
(!CanGo(Next)) continue;
If the position Next is an uncut cell and we haven’t been there yet, then we go there. In the array of
ancestors, we note that we got to Next
from the cell Node.
if
((s[Next.x][Next.y] != '#') &&
(Parent[Next.x][Next.y] ==
EMPTY_CELL))
{
Parent[Next.x][Next.y] = Node;
If we came to the final vertex Finish, then we
should stop the search.
if
(Next == Finish) return;
Move the cell Next to the end of the queue d.
d.push_back(Next);
}
}
}
}
The main part of
the program. Perform the
initialization of variables. Read the state of the chessboard into the array s. The
coordinates of the initial and final positions of the knight, marked on the board with
the @ symbol, are stored in the variables Start and Finish of type CELL.
scanf("%d\n",&n);
for(i = 0; i < n; i++) gets(s[i]);
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if (s[i][j]
== '@')
{
if (Start.x
== -1) {Start.x = i; Start.y = j;}
else
{Finish.x = i; Finish.y = j;}
}
Start the breadth first search from the cell Start.
bfs(Start);
We could complete the breadth first search by fulfilling one of the two conditions: either all the vertices that can be reached
by the knight from the cell Start were visited and the queue d became empty, or at some point in time we came
to Finish and exited the bfs function.
If the depth first search does not reach the cell Finish, then the required knight path does not exist.
if (Parent[Finish.x][Finish.y] ==
EMPTY_CELL) printf("Impossible\n");
else
{
If the shortest path from Start
to Finish exists, then using the array of ancestors, we restore it. The
shortest path of the knight is
filled with @ symbols.
s[Start.x][Start.y] = '@';
while(Start
!= Finish)
{
s[Finish.x][Finish.y] = '@';
Finish = Parent[Finish.x][Finish.y];
}
Print the resulting chessboard.
for(i = 0; i
< n; i++) puts(s[i]);
}