Dayi Lin, Ph.D.

Principal Researcher, AI & Software Engineering

POJ-1753 解题报告

POJ

题意简述

4*4的格子放有黑白两面的棋子16个,翻转任一棋子会使其上下左右棋子一同翻转。给定初始状态,求达到所有棋子全黑或全白的最少翻转次数。如果无解,输出Impossible。

POJ1753附图

POJ1753附图

算法分析

首先容易证明:

1、翻转棋盘上任意个棋子,棋盘达到的状态与各棋子被翻转的先后顺序无关。

2、对每个棋子进行2次及以上的翻转没有意义。∵ 偶数次翻转结果与不翻转相同,奇数次翻转结果与翻转1次相同。

于是问题被简化为:棋盘上部分棋子经过1次翻转,能使棋盘达到全黑或全白状态。求所需翻转棋子的最少数目。

因为一共只有16个棋子,故只有2^16种可能。

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

具体算法:

DFS。

输入时将数据转化为1维01数组。

dfs(array,position,step,answer)四个形参,array传递数组,position传递当前位置,step传递深度(也即翻转个数),ans传递当前最优答案。

深搜时先判断当前状态是否满足条件,满足则和当前答案对比,若更优则替换。返回。

若深度超出16也返回。

改变当前位置,以及上下左右共5个点状态。

dfs(array,position+1,step+1,answer)

回溯。只需再次改变5个点状态即可。

dfs(array,position+1,step,answer)

Problem Status: AC。时间94ms,内存360k

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

TIPS:

WA了好几次。有几个小细节要注意:

1、翻转时,如果遇到行末则不翻转下一个,遇到行首则不翻转上一个。可以通过mod 4的值来判断。

2、DFS时,需先判断是否满足条件(全黑或全白)再判断位置是否越界(position<16)。因为有可能所有棋子都需要翻转,由于判断本次翻转是否成功是在下一层递归中,所以即使position越界也需先验证一次上次翻转后是否达到所需状态。

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

优化:

1、一维01数组可以使用一个int类型变量替代。2个字节16位就可以表示了。翻转操作采用位运算实现。(这个还没试过,据说时间达到16ms,以后有机会试下。)

2、网上的解题报告说据说有一种枚举可以达到时间0ms?还没找到具体算法。要去膜拜下。

程序样例

#include<stdio.h>

void change(int s[], int pos) {
  if (s[pos] == 0) s[pos] = 1;
  else s[pos] = 0;
  if ((pos + 1 < 16) && (pos % 4 != 3))
    if (s[pos + 1] == 0) s[pos + 1] = 1;
    else s[pos + 1] = 0;
  if ((pos - 1 >= 0) && (pos % 4 != 0))
    if (s[pos - 1] == 0) s[pos - 1] = 1;
    else s[pos - 1] = 0;
  if (pos + 4 < 16)
    if (s[pos + 4] == 0) s[pos + 4] = 1;
    else s[pos + 4] = 0;
  if (pos - 4 >= 0)
    if (s[pos - 4] == 0) s[pos - 4] = 1;
    else s[pos - 4] = 0;
}

int finish(int s[]) {
  int i;
  for (i = 1; i < 16; i++)
    if (s[i] != s[0]) return 0;
  return 1;
}

void
try (int s[], int pos, int step, int * ans) {
  if (finish(s)) {
    if (step < * ans) * ans = step;
    return;
  }
  if (pos > 15) return;
  change(s, pos);
  try (s, pos + 1, step + 1, ans);
  change(s, pos);
  try (s, pos + 1, step, ans);
}

int main() {
  int s[16];
  int i, j, ans = 17;
  char t[5];
  for (i = 0; i < 4; i++) {
    scanf("%s", t);
    for (j = 0; j < 4; j++)
      if (t[j] == 'b') s[i * 4 + j] = 1;
      else s[i * 4 + j] = 0;
  }
  try (s, 0, 0, & ans);
  if (ans == 17) printf("Impossible");
  else printf("%d", ans);
  system("pause");
  return 0;
}

Leave a Reply

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