Dayi Lin, Ph.D.

Principal Researcher, AI & Software Engineering

POJ-2996 解题报告

POJ

题意简述

将一个棋盘翻译为文字表达。如下:

+---+---+---+---+---+---+---+---+
|.r.|:::|.b.|:q:|.k.|:::|.n.|:r:|
+---+---+---+---+---+---+---+---+
|:p:|.p.|:p:|.p.|:p:|.p.|:::|.p.|
+---+---+---+---+---+---+---+---+
|...|:::|.n.|:::|...|:::|...|:p:|
+---+---+---+---+---+---+---+---+
|:::|...|:::|...|:::|...|:::|...|
+---+---+---+---+---+---+---+---+
|...|:::|...|:::|.P.|:::|...|:::|
+---+---+---+---+---+---+---+---+
|:P:|...|:::|...|:::|...|:::|...|
+---+---+---+---+---+---+---+---+
|.P.|:::|.P.|:P:|...|:P:|.P.|:P:|
+---+---+---+---+---+---+---+---+
|:R:|.N.|:B:|.Q.|:K:|.B.|:::|.R.|
+---+---+---+---+---+---+---+---+

大写字母表示白方,小写表示黑方。输出时按照KQRBNP的顺序;棋盘格子编号的表示:从下往上是1~8,从左往右是a~h。

遇到相同棋子,白方表示时按从下往上从左往右的顺序,黑方按从上往下从左往右的顺序。

输出格式:

White: Ke1,Qd1,Ra1,Rh1,Bc1,Bf1,Nb1,a2,c2,d2,f2,g2,h2,a3,e4
Black: Ke8,Qd8,Ra8,Rh8,Bc8,Ng8,Nc6,a7,b7,c7,d7,e7,f7,h7,h6

算法分析

直接模拟。

分行读入棋盘,分析该行字母,将对应坐标记录。此处忽略黑白相同棋子从上往下和从下往上的区别,只需满足从上往下从左往右。

输出时黑子按存储的顺序输出即可,白子输出相同棋子时判断,若有相同棋子则先输出行数大的。

具体实现见代码。

Problem Status: AC。时间0ms,内存388k

——————————————————————分割线——————————————————————

注意棋子是有规律的,最多16个,但可以不全出现。KQ各一个,RBN最多两个,P8个。

程序样例

#include<stdio.h>

void outputb(int a[16][2]) {
  int i;
  if (a[0][0]) printf("K%c%d", 'a' + a[0][1] - 1, 9 - a[0][0]);
  if (a[1][0]) printf(",Q%c%d", 'a' + a[1][1] - 1, 9 - a[1][0]);
  if (a[2][0]) printf(",R%c%d", 'a' + a[2][1] - 1, 9 - a[2][0]);
  if (a[3][0]) printf(",R%c%d", 'a' + a[3][1] - 1, 9 - a[3][0]);
  if (a[4][0]) printf(",B%c%d", 'a' + a[4][1] - 1, 9 - a[4][0]);
  if (a[5][0]) printf(",B%c%d", 'a' + a[5][1] - 1, 9 - a[5][0]);
  if (a[6][0]) printf(",N%c%d", 'a' + a[6][1] - 1, 9 - a[6][0]);
  if (a[7][0]) printf(",N%c%d", 'a' + a[7][1] - 1, 9 - a[7][0]);
  for (i = 8; i < 16; i++)
    if (a[i][0]) printf(",%c%d", 'a' + a[i][1] - 1, 9 - a[i][0]);
}

void outputw(int a[16][2]) {
  int i, j;
  if (a[0][0]) printf("K%c%d", 'a' + a[0][1] - 1, 9 - a[0][0]);
  if (a[1][0]) printf(",Q%c%d", 'a' + a[1][1] - 1, 9 - a[1][0]);
  if (a[2][0] < a[3][0]) {
    if (a[3][0]) printf(",R%c%d", 'a' + a[3][1] - 1, 9 - a[3][0]);
    if (a[2][0]) printf(",R%c%d", 'a' + a[2][1] - 1, 9 - a[2][0]);
  } else {
    if (a[2][0]) printf(",R%c%d", 'a' + a[2][1] - 1, 9 - a[2][0]);
    if (a[3][0]) printf(",R%c%d", 'a' + a[3][1] - 1, 9 - a[3][0]);
  }
  if (a[4][0] < a[5][0]) {
    if (a[5][0]) printf(",B%c%d", 'a' + a[5][1] - 1, 9 - a[5][0]);
    if (a[4][0]) printf(",B%c%d", 'a' + a[4][1] - 1, 9 - a[4][0]);
  } else {
    if (a[4][0]) printf(",B%c%d", 'a' + a[4][1] - 1, 9 - a[4][0]);
    if (a[5][0]) printf(",B%c%d", 'a' + a[5][1] - 1, 9 - a[5][0]);
  }
  if (a[6][0] < a[7][0]) {
    if (a[7][0]) printf(",N%c%d", 'a' + a[7][1] - 1, 9 - a[7][0]);
    if (a[6][0]) printf(",N%c%d", 'a' + a[6][1] - 1, 9 - a[6][0]);
  } else {
    if (a[6][0]) printf(",N%c%d", 'a' + a[6][1] - 1, 9 - a[6][0]);
    if (a[7][0]) printf(",N%c%d", 'a' + a[7][1] - 1, 9 - a[7][0]);
  }
  for (j = 8; j > 0; j--)
    for (i = 8; i < 16; i++)
      if (a[i][0] && a[i][0] == j) printf(",%c%d", 'a' + a[i][1] - 1, 9 - a[i][0]);
}

int main() {
  char t[50];
  int i, j, p = 0, p1 = 0;
  int white[16][2] = {
    0
  }, black[16][2] = {
    0
  };
  scanf("%s", t);
  for (i = 0; i < 8; i++) {
    scanf("%s", t);
    for (j = 2; j < 33; j = j + 4) {
      switch (t[j]) {
      case 'k':
        black[0][0] = i + 1;
        black[0][1] = (j - 2) / 4 + 1;
        break;
      case 'q':
        black[1][0] = i + 1;
        black[1][1] = (j - 2) / 4 + 1;
        break;
      case 'r':
        if (black[2][0]) {
          black[3][0] = i + 1;
          black[3][1] = (j - 2) / 4 + 1;
          break;
        } else {
          black[2][0] = i + 1;
          black[2][1] = (j - 2) / 4 + 1;
          break;
        }
      case 'b':
        if (black[4][0]) {
          black[5][0] = i + 1;
          black[5][1] = (j - 2) / 4 + 1;
          break;
        } else {
          black[4][0] = i + 1;
          black[4][1] = (j - 2) / 4 + 1;
          break;
        }
      case 'n':
        if (black[6][0]) {
          black[7][0] = i + 1;
          black[7][1] = (j - 2) / 4 + 1;
          break;
        } else {
          black[6][0] = i + 1;
          black[6][1] = (j - 2) / 4 + 1;
          break;
        }
      case 'p':
        black[8 + p][0] = i + 1;
        black[8 + p][1] = (j - 2) / 4 + 1;
        p++;
        break;
        //white
      case 'K':
        white[0][0] = i + 1;
        white[0][1] = (j - 2) / 4 + 1;
        break;
      case 'Q':
        white[1][0] = i + 1;
        white[1][1] = (j - 2) / 4 + 1;
        break;
      case 'R':
        if (white[2][0]) {
          white[3][0] = i + 1;
          white[3][1] = (j - 2) / 4 + 1;
          break;
        } else {
          white[2][0] = i + 1;
          white[2][1] = (j - 2) / 4 + 1;
          break;
        }
      case 'B':
        if (white[4][0]) {
          white[5][0] = i + 1;
          white[5][1] = (j - 2) / 4 + 1;
          break;
        } else {
          white[4][0] = i + 1;
          white[4][1] = (j - 2) / 4 + 1;
          break;
        }
      case 'N':
        if (white[6][0]) {
          white[7][0] = i + 1;
          white[7][1] = (j - 2) / 4 + 1;
          break;
        } else {
          white[6][0] = i + 1;
          white[6][1] = (j - 2) / 4 + 1;
          break;
        }
      case 'P':
        white[8 + p1][0] = i + 1;
        white[8 + p1][1] = (j - 2) / 4 + 1;
        p1++;
        break;
      }
    }
    scanf("%s", t);
  }
  printf("White: ");
  outputw(white);
  printf("\nBlack: ");
  outputb(black);
  printf("\n");

  system("pause");
  return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *