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
2b
2c
3d
4f
5d
7a
7d
7g
0

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;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
#1146 Beecrowd Online Judge Solution 1146 Growing Sequences Solution in C++, Java, Js and Python
Next
#1149 Beecrowd Online Judge Solution 1149 Summing Consecutive Integers Solution in C++, Java, Js and Python