Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1343
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1343
Runner Pawns
Por Sergio Gabriel Tavares 
Brazil
Timelimit: 1
The “Runner Pawns” game is a variant of classic Chess for a single player. It uses a board similar to the chess board, divided in 8x8 squares. As in chess, each square can contain only one piece at a time. The pieces are a number of pawns (the “Runner Pawns”), and a single horse, which is the only piece under command of the player. The objective is to capture all pawns before they get to the last row and become kings.
Possible movements of the horse
Horse moves are said to be in 'L' shape, since a horse must always move two squares in one direction and one square in the perpendicular direction. The figure above illustrates horse movements, where the character 'H' indicates the horse current position, and the character '•' indicates possible final positions. Notice that in the representation used black and white squares of the chess board are not distinguished.
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 From position 22, the horse can move to positions 05,
33 34 35 36 37 38 39 40 07, 12, 16, 28, 32, 37 or 39. From position 57, the
41 42 43 44 45 46 47 48 horse can move to positions 42 or 51.
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
A board with cells numbered
Pawns' moves are a bit different from chess, since they can only move one square forward, and all of them move at the same time. They never move on a diagonal. Squares of the board are numbered from 1 to 64, as shown above. Pawns move in vertical direction from top to bottom, so that squares numbered 57 to 64 are the pawns' goal.
Each round of the game is composed by one move of the horse followed by a simultaneous move of all pawns not yet captured.
In order to capture a pawn, the player has to move the horse to a square where a pawn is. A captured pawn leaves the board, and only the remaining ones will move ahead in the next round. To win the game, the player has to capture all pawns. If a pawn gets to the last row, it becomes a king. Then the horse has only one more move to capture it. If it doesn’t, the king moves and it means that the game is over and the player loses. Moreover, if the horse moves to a square that will be occupied by a pawn at the next move of the pawns, the horse is captured by the pawn and the player loses.
Your task is to write a program that analysis a "Runner Pawns" diagram and answer whether there is a sequence of movements for the horse to win. If it is possible, your program should determine the minimum number of moves needed by the horse to capture all pawns.
Input
The input contains several instances of the problem, one per line. Each instance starts with an integer P representing the number of pawns (0 ≤ P ≤ 8), followed by P integers (1 ≤ A1, A2, ... AP ≤ 64) that describe the initial position of each pawn, followed by an integer H (1 ≤ H ≤ 64) representing the starting position of the horse. The end of input is indicated by a line containing P = 0.
Output
For each instance of the problem in the input your program must print a single line, containing the answer to the problem. If there is a sequence of moves for the horse to capture all pawns before a surviving king moves (and without the horse being captured by a pawn) then the program should print the length of the minimum sequence of moves that make it possible. Otherwise your program should print the word ‘impossible’.
| Sample Input | Sample Output |
|
1 1 11 |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_set>
#include <vector>
#define pb push_back
#define mp make_pair
using namespace std;
typedef unsigned long long int64;
typedef pair < int, int> ii;
map<int, ii> positions;
unordered_set < string> visited;
char g_matrix[8][8];
int dir[][2] = {
{ -1, -2 }, { -2, -1 }, { -2, 1 }, { -1, 2 }, { 1, -2 }, { 2, -1 }, { 2, 1 }, { 1, 2 }
};
struct edge {
int x, y, count;
char matrix[8][8];
vector < ii> pawns;
edge(int x = 0, int y = 0, int count = 0)
: x(x)
, y(y)
, count(count)
{
}
string getHash()
{
string resp = "";
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++)
resp += matrix[i][j];
resp += '*';
}
return resp;
}
};
void initialize()
{
int k = 0;
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
positions[k++] = mp(i, j);
}
void capture(ii pos, edge& e)
{
for (int i = 0; i < e.pawns.size(); i++) {
if (e.pawns[i] == pos) {
e.matrix[pos.first][pos.second] = 'h';
e.pawns.erase(e.pawns.begin() + i);
return;
}
}
}
bool movePawns(edge& e)
{
for (int i = 0; i < e.pawns.size(); i++)
e.matrix[e.pawns[i].first][e.pawns[i].second] = '.';
for (int i = 0; i < e.pawns.size(); i++) {
ii a = e.pawns[i];
e.pawns[i].first++;
if (e.pawns[i].first > 7)
return true; //couldn't capture this one
if (e.matrix[a.first + 1][a.second] == 'h')
return true; //just got hit by a pawn!
e.matrix[a.first + 1][a.second] = 'p';
}
return false;
}
int bfs(int x, int y, vector < ii>& pawns)
{
queue b;
edge aux = edge(x, y, 0);
memcpy(aux.matrix, g_matrix, sizeof(aux.matrix));
aux.pawns = pawns;
b.push(aux);
//horse has the first move
bool horseMove = true;
while (!b.empty()) {
aux = b.front();
b.pop();
if (!horseMove && movePawns(aux))
continue;
horseMove = false;
for (int i = 0; i < 8; i++) {
//original state
edge e = aux;
memcpy(e.matrix, aux.matrix, sizeof(e.matrix));
e.pawns = aux.pawns;
int p1 = e.x + dir[i][0];
int p2 = e.y + dir[i][1];
if (p1 < 0 || p2 < 0 || p1 > 7 || p2 > 7)
continue;
if (e.matrix[p1][p2] == 'p') {
e.matrix[e.x][e.y] = '.';
capture(mp(p1, p2), e);
} else {
e.matrix[e.x][e.y] = '.';
e.matrix[p1][p2] = 'h';
}
string state = e.getHash();
if (visited.count(state))
continue;
visited.insert(state);
e.x = p1;
e.y = p2;
e.count++;
if (!e.pawns.size())
return e.count; //captured all of them
b.push(e);
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
initialize();
int n, p, h;
while (cin >> n && n) {
ii a;
vector < ii> pawns;
memset(g_matrix, '.', sizeof(g_matrix));
while (n--) {
cin >> p;
a = positions[p - 1];
g_matrix[a.first][a.second] = 'p';
pawns.pb(a);
}
cin >> h;
a = positions[h - 1];
g_matrix[a.first][a.second] = 'h';
int resp = bfs(a.first, a.second, pawns);
if (resp != -1)
cout << resp << "\n";
else
cout << "impossible\n";
visited.clear();
}
return 0;
}
Input
Output