编程介的小学生 2017-03-08 08:01 采纳率: 20.5%
浏览 732
已采纳

Deeper Blue

Introduction

When trying to avoid conflict and maintain peace, a good strategy is to remove the elements that cause the most trouble. IBM is using its Deep Blue machine to try to study this strategy by modeling it with a game of chess. IBM needs a program to find the minimum number of chess pieces that must be removed from a chessboard in order for none of the pieces to be attacking each other.

All pieces will have the standard attack movements for that chess piece.

King - Can attack the adjacent space in any direction. Up, down, left, right and diagonally.

Queen - Can attack any number of spaces in any direction. Up, down, left, right and diagonally.

Bishop - Can attack any number of spaces diagonally.

Rook - Can attack any number of spaces up, down, left, or right but not diagonally.

Pawns - There won't be any pawns.

Knight - Can attack with their usual 'L' shaped movement. Up twice and right once, up once and left twice, etc... Here is a diagram, which demonstrates the movement of a knight.


| | |*| |*| | |

| |*| | | |*| |

| | | |N| | | |

| |*| | | |*| |

| | |*| |*| | |

N = Knight

  • = Square that the knight can attack

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets. The maximum dimensions of the board are 10 squares wide by 10 squares high. The maximum number of chess pieces that will start out on the board is 15.

A single data set has 5 components:

Start line - A single line, "START"

Board Width (# of columns) - A single line containing a positive integer, w, indicating the number of squares across the width of the board where 1 <= w <= 10.

Board Height (# of rows) - A single line containing a positive integer, h, indicating the number of squares that dictate the height of the board, where 1 <= h <= 10.

Board Layout - h lines, each corresponding to a row of the board. The first line corresponds to the first row, the second line to the second row, and so on. Each row consists of a space-separated list of single letters, each representing the contents of the corresponding square on the board according to the following list:

K - King
Q - Queen
R - Rook
B - Bishop
N - Knight
E - Empty Square

End line - A single line, "END"

Output

For each data set, there will be exactly one output set, and there will be no blank lines separating output sets.

A single output set consists of a single line, "Minimum Number of Pieces to be removed: X", where X is the minimum number of pieces that must be removed from the board such that none of the remaining pieces are attacking any other remaining piece.

Sample Input

START
3
3
K E K
E Q E
K E K
END
START
8
8
E E E E E E E E
E B E K E E N E
E E E E N E E E
E E E E E E E R
B E Q E E E E E
E E E E E Q E E
E E E E E B E E
E B E R E E E E
END

Sample Output

Minimum Number of Pieces to be removed: 1
Minimum Number of Pieces to be removed: 5

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-03-09 10:56
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常