POJ-2965 解题报告

题意简述

4*4矩阵，填充+或-，改变某格符号将同时改变当前行和列所有的格的符号。

求最少经过多少次转换能使所有符号变为-，并输出任一种可行方案。

算法分析

本题与POJ-1753基本没有区别。仅仅换了壳，增加了输出一种可行方案。

【POJ-1753解题报告 传送门】

在POJ-1753的基础上，DFS同时用一个16个一维01数组记录当前的转换方案。与当前最优解比较时，如果更优则替换已记录的最优方案。

Problem Status: AC。时间875ms，内存388k

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

优化：

1、与POJ-1753一样可以使用一个int型代替一维01数组，用位运算实现转换。（还没试，改天再说…）

2、在评测记录里看到一个内存16K，时间0ms的记录…估计和POJ-1753一样用了某种神奇的枚举…如果找到了代码或者算法会更新上来~

程序样例

#include<stdio.h>

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

void change(int s[], int pos) {
  int i;
  if (s[pos] == 1) s[pos] = 0;
  else s[pos] = 1;
  for (i = 0; i < 16; i++)
    if (i != pos) {
      if (i % 4 == pos % 4)
        if (s[i] == 1) s[i] = 0;
        else s[i] = 1;
      if (i / 4 == pos / 4)
        if (s[i] == 1) s[i] = 0;
        else s[i] = 1;
    }
}

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

int main() {
  int s[16];
  int i, j, ans = 17, a[16] = {
    0
  }, at[16] = {
    0
  };
  char t[5];
  for (i = 0; i < 4; i++) {
    scanf("%s", t);
    for (j = 0; j < 4; j++)
      if (t[j] == '-') s[i * 4 + j] = 1;
      else s[i * 4 + j] = 0;
  }
  try (s, at, a, 0, 0, & ans);
  printf("%d\n", ans);
  for (i = 0; i < 16; i++)
    if (a[i] == 1) printf("%d %d\n", i / 4 + 1, i % 4 + 1);
  return 0;
}