Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1147
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1147
Knight Scape
By Gerson Groth 
Brazil
Timelimit: 1
Your friend Peter is learning chess. But he's still amateur and doesn't have enough conviction to make secure movements of the knight piece. This way, Peter asked you to make a program that calculate, in one turn, the distinct possible movements that the knight can perform, without be on attack of any of the 8 existing pawns. The knight's movements and pawn's movements are according to the chess rules, that means the knight must move in L and the pawn must move one square to any direction, without going back. Look the following example.
In the picture, considering all 8 possible positions to move the Knight, two of them are under attack (6b and 3e). In the other squares, the knight can be moved without problem, escaping this way of the any pawn attack. In the 2b square a pawn already exists, but is also a valid moviment to the knight, because it can go to this position and "kill" the pawn.
So, as the given example, the secure (valid) movements are 6. You must remember that the black pawn can move from up to down int the table, from line 7 to line 1.
Input
The input file consist in many test cases. Each test case consist in 9 input lines. The first line indicates the initial position of the knight. The following 8 lines describe the respectively pawn positions.
The last line of the input file contains only the number 0 (Zero).
Output
For each test case your program must print an unique line, containig the descrition:
Caso de Teste #Y: X movimento(s).
Where Y represents the test case, X represents the among of possible secure movements to the knight without be on pawn attack.
| Input Sample | Output Sample |
|
4c |
Caso de Teste #1: 6 movimento(s). |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
int d_x[] = {1,1,2,2,-1,-1,-2,-2},
d_y[] = {2,-2,1,-1,2,-2,1,-1};
int main()
{
freopen("in.txt","r",stdin);
ios_base::sync_with_stdio(false);cin.tie(NULL);
int idx = 0,n;
char ch;
while(cin >> n >> ch and n ){
int res = 0;
vector < vector < int> > ans(8, vector<int>(8));
int x = n - 1,
y = ch - 'a';
for(int i = 0; i < 8 ; i++){
cin >> n >> ch;
ans[n - 1][ch - 'a'] = 1;
}
for(int i = 0; i < 8 ; i++){
int x1 = x + d_x[i],
y1 = y + d_y[i];
if(x1 >= 0 and x1 < 8 and y1 >= 0 and y1 < 8){
int x2 = x1 + 1,
y2 = y1 - 1,
k = 1;
if(x2 >= 0 and x2 < 8 and y2 >= 0 and y2 < 8 and ans[x2][y2]) k = 0;
y2 = y1 + 1;
if(x2 >= 0 and x2 < 8 and y2 >= 0 and y2 < 8 and ans[x2][y2]) k = 0;
if(k) res++;
}
}
cout << "Caso de Teste #" << ++idx << ": " << res << " movimento(s)." << endl;
}
return 0;
}