某网站的题解标点符号的要求真是a piece of bloody shit. 在这里会自由一些.
0. 题目大意
题目的大意是模拟黑白棋游戏。简单而言有如下的要求：
- 列出可能的移动。合法移动的规则是：新下的棋子必须 "夹住" 原来的。所谓夹住，其实就是一段横向、竖向、斜向的棋子之间的两段必须是另外一种颜色的。没有移动的时候输出「No legal move.」
- 在某一个地方移动合法的一位。如果当前的这一手没有合法的移动，那么自动切换到另一手。移动之后，所有被夹住的棋子都会变成另一个颜色。完成之后输出棋盘上面有多少的黑、白棋子。
- 退出棋盘。退出的时候画出棋盘的样子。就像输入那样。
本问题有一些小的细节注意点，总结如下：
- 注意每一个行的末尾不要有多余的空格。可能是和 UVA 的全文严格匹配的缘故。
- 样例与样例之间有一个整个的空行，但是末尾只有一个空行而不是两个。
- 由于空格的格式限制，可以使用
printf("Black -%3d White -%3d\n", ...);的格式来做。因为%nd是固定宽度的提示符（这是怎么实现的？可以参看《The C Programming Language 2nd Edition》的 7.2 节，解释了这样的一个变长参数的函数定义，C 是如何处理的）。
1. 读入
这里简单采取 getchar 进行读入。注意，其同样处理换行符。因此需要把换行符过滤掉。也就是每行的末尾也要加一个 getchar()。读入数组即可。
int work(){
getchar(); // 过滤掉空格
// b 是我们读入的棋盘
memset(b, 0, sizeof b);
for(int i=1; i<=8; i++){
for(int j=1; j<=8; j++){
b[i][j] = getchar();
}
getchar();
}
// 当前操作的是谁？
curr = getchar();
string s;
do{
cin>>s;
if(s[0] == 'L'){
check(curr, true);
}else if(s[0] == 'M'){
int xx = s[1]-'0', yy = s[2]-'0';
makemv(xx, yy);
// NOT_B 是另一种颜色，由宏定义。
curr = NOT_B(curr);
}
}while(s != "Q");
visualize(false);
return 0;
}
2. 八个方向的搜索
对于第一个要求，可以使用如下的策略：枚举每一个格子，如果发现是和当前操作的是一样的，那就可以以它为 "支点" 往外延伸，看一看是不是为空。这里方向使用了 dx 与 dy 两个数组，表示了延伸的方向。
接下来是去重与排序的问题。可以使用 pair<int, int> 表示坐标。然后去重的时候先排序，再调用。具体代码如下：
// 可能的8个移动方向
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int check(char which, bool out){
char t[N][N];
memcpy(t, b, sizeof b);
vector<Pos> pos;
// 枚举搜索方向
for(int k=0; k<8; k++)
// 枚举位置 (i, j)
for(int i=1; i<=8; i++)
for(int j=1; j<=8; j++){
if(t[i][j]==which){
int tmpx = i, tmpy = j;
// 夹住的棋子计数
int ncnt = -1;
do{
ncnt++;
tmpx += dx[k], tmpy += dy[k];
}while(t[tmpx][tmpy]==NOT_B(which));
if(t[tmpx][tmpy]==EMPTY && ncnt>0 && IN_PLACE(tmpx, tmpy))
pos.push_back(make_pair(tmpx, tmpy));
}
}
if(pos.size() == 0) {
if(out) printf("No legal move.\n");
return 0;
}
if(!out) return pos.size();
// 按照要求输出。
sort(pos.begin(), pos.end());
auto it = unique(pos.begin(), pos.end());
pos.erase(it, pos.end());
for(int idx = 0; idx<pos.size(); idx++){
auto i = pos[idx];
printf("(%d,%d)", i.first, i.second);
if(idx != pos.size()-1) printf(" ");
}
printf("\n");
return pos.size();
}
同样的，试图移动的时候和这个的过程也类似。找遍八个方向看一看有没有被夹着的。如果有，把它们反过来。有如下的代码：
void makemv(int x, int y){
// 没有合法移动，切换当前颜色。
if(check(curr, false) == 0) curr = NOT_B(curr);
char t[N][N];
memcpy(t, b, sizeof b);
t[x][y] = curr;
for(int dir = 0; dir<8; dir++){
int tmpx = x, tmpy = y, ncnt = -1;
do{
ncnt++;
tmpx += dx[dir], tmpy += dy[dir];
}while( IN_PLACE(tmpx, tmpy) && t[tmp
x][tmpy]== NOT_B(curr));
if(t[tmpx][tmpy] != curr ){
continue;
}
int i=tmpx, j=tmpy;
while(ncnt--){
i-=dx[dir], j-=dy[dir];
t[i][j] = NOT_B(t[i][j]);
}
}
memcpy(b, t, sizeof b);
count();
}
count() 是数一数当前有多少个黑、多少个白。如下：
void count(){
int nb=0, nw=0;
for(int i=1; i<=8; i++)
for(int j=1; j<=8; j++){
if(b[i][j] == BLACK) nb++;
if(b[i][j] == WHITE) nw++;
}
printf("Black -%3d White -%3d\n", nb, nw);
}
这就是整个的流程了。下面我们给出整体的代码。
3. 总体代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
// Board configuration
#define N 10
// Board chess configuration
#define WHITE 'W'
#define BLACK 'B'
#define EMPTY '-'
#define NOT_B(x) (x=='B'?'W':'B')
#define IN_PLACE(x, y) (x>=1 && x<=8 && y>=1 && y<=8)
char b[N][N];
char hand;
int T=-1;
void visualize(bool aux_line){
for(int i=1; i<=8; i++){
for(int j=1; j<=8; j++){
if(b[i][j]==0){ cout<<"-"; }
else {cout<<b[i][j];}
}
if(T!=0 || i != 8)cout<<endl;
}
}
typedef pair<int, int> Pos;
// Possible 8 movements
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int check(char which, bool out){
char t[N][N];
memcpy(t, b, sizeof b);
vector<Pos> pos;
// Enumerate the searching direction
for(int k=0; k<8; k++)
// Enumerate the position (i, j)
for(int i=1; i<=8; i++)
for(int j=1; j<=8; j++){
if(t[i][j]==which){
int tmpx = i, tmpy = j;
// count of the chess in between
int ncnt = -1;
do{
ncnt++;
tmpx += dx[k], tmpy += dy[k];
}while(t[tmpx][tmpy]==NOT_B(which));
if(t[tmpx][tmpy]==EMPTY && ncnt>0 && IN_PLACE(tmpx, tmpy))
pos.push_back(make_pair(tmpx, tmpy));
}
}
if(pos.size() == 0) {
if(out) printf("No legal move.\n");
return 0;
}
if(!out) return pos.size();
// Output as required.
sort(pos.begin(), pos.end());
auto it = unique(pos.begin(), pos.end());
pos.erase(it, pos.end());
for(int idx = 0; idx<pos.size(); idx++){
auto i = pos[idx];
printf("(%d,%d)", i.first, i.second);
if(idx != pos.size()-1) printf(" ");
}
printf("\n");
return pos.size();
}
void count(){
int nb=0, nw=0;
for(int i=1; i<=8; i++)
for(int j=1; j<=8; j++){
if(b[i][j] == BLACK) nb++;
if(b[i][j] == WHITE) nw++;
}
printf("Black -%3d White -%3d\n", nb, nw);
}
void makemv(int x, int y){
if(check(hand, false) == 0) hand = NOT_B(hand);
char t[N][N];
memcpy(t, b, sizeof b);
t[x][y] = hand;
for(int dir = 0; dir<8; dir++){
int tmpx = x, tmpy = y, ncnt = -1;
do{
ncnt++;
tmpx += dx[dir], tmpy += dy[dir];
}while( IN_PLACE(tmpx, tmpy) && t[tmpx][tmpy]== NOT_B(hand));
if(t[tmpx][tmpy] != hand ){
continue;
}
int i=tmpx, j=tmpy;
while(ncnt--){
i-=dx[dir], j-=dy[dir];
t[i][j] = NOT_B(t[i][j]);
}
}
memcpy(b, t, sizeof b);
count();
}
int work(){
getchar(); // Filter out the space
memset(b, 0, sizeof b);
for(int i=1; i<=8; i++){
for(int j=1; j<=8; j++){
b[i][j] = getchar();
}
getchar();
}
hand = getchar();
string s;
do{
cin>>s;
if(s[0] == 'L'){
check(hand, true);
}else if(s[0] == 'M'){
int xx = s[1]-'0', yy = s[2]-'0';
makemv(xx, yy);
hand = NOT_B(hand);
}
}while(s != "Q");
visualize(false);
return 0;
}
int main(){
cin>>T; while(T--) {work(); printf("\n");}
return 0;
}