ZOJ Problem Set - 3262
On the chess board, the poor little pawns are put out in front right in harms way while the other guys are hiding back behind.But according the chess rules, if a pawn can make it to the other side, it will be rewarded with a promotion - to a queen! Noting this, EZ invents a new kind of single-player game.
At the beginning of the game, EZ puts 8 black pawns on the first rank(see the figure below), and then places some enemy on the board. He wonder how many of them can become queens at most.
Here are some rules in this game about the move of the pawn. You can see more detail in Rules of Chess
There are multiple cases (no more than 30). The first line of each test case contains an integer N, indicating the number of enemys on the board. (0 <= N <= 16) Then N lines followed, each line contains two character cr ('a' <= c <= 'h', '1' < r <= '8'), which is the loction of the ith enemy.
For each case, output the maximum number of pawns that can be promoted to queens in a single line.
2 a2 b2 3 a2 b2 e5 3 a2 b2 b3
8 7 8
Author: WANG, Yelei
Source: ZOJ Monthly, November 2009