Poj 1753

刚被室友坑去写这题了,水题来的。

就是翻转棋,但是数据规模仅有4x4

既然4x4的话,黑白两色状态,那么就是216-1个状态,也就是说直接宽搜就可以了。

说起宽搜那就一定要做判重,判重就要记录搜索的数据,记录搜索数据那就要用二进制压缩咯。

我们可以用位运算来优化一下:

1
2
3
4
5
6
7
8
int
flip(int x, int y, int source)
{
  x = 3 - x;
  y = 3 - y;
  int tmp = y * 4 + x;
  return source ^ (1 << tmp);
}

这样就把x y 直接映射到 int 上去了

之后就没什么了,爆搜即可,由于我这里用的c 写的,没stl,写的就略丑…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 65536
int DD[5][2] = { {0,0}, {0,1}, {0,-1}, {-1,0}, {1,0} };

struct _queue_struct
{
  int x, step;
};

typedef struct _queue_struct queue_struct;
queue_struct queue[MAXN];

int queue_head, queue_tail;
short flag[MAXN];

int
flip(int x, int y, int source)
{
  x = 3 - x;
  y = 3 - y;
  int tmp = y * 4 + x;
  return source ^ (1 << tmp);
}

void
initial_queue(int s)
{
  for (int i = 0; i < MAXN; ++i)
  {
      queue[i].step = 0;
      queue[i].x = -1;
      flag[i] = 0;
  }
    queue_head = queue_tail = 0;
  queue[0].x = s;
  queue[0].step = 0;
  flag[s] = 1;
}

int
checkLegal(int x, int y)
{
  return (x >= 0) && (x < 4) && (y >= 0) && (y < 4);
}

int main()
{
  int i, j;
  int s = 0; //all white
  for (i = 0; i < 4; i++)
      for (j = 0; j < 4; j++)
      {
          char ch;
          scanf("%c", &ch);
            while (ch == '\n')
            {
                scanf("%c", &ch);
            }

          if (ch == 'b')
              s = flip(j, i, s);
      }
  
    if (s == 65535 || s == 0)
    {
        printf("0\n");
        return 0;
    }
  initial_queue(s);
  
  while (queue_tail >= queue_head)
  {
      queue_struct v = queue[queue_head];

      for (i = 0; i < 16; ++i)
      {
          int tmp = v.x;
          for (j = 0; j < 5; ++j)
          {
              int x = i % 4 + DD[j][0], y = i / 4 + DD[j][1];

              if (checkLegal(x, y))
                  tmp = flip(x, y, tmp);
          }
          
          if (!flag[tmp])
          {
              if ((tmp == 0) || (tmp == MAXN-1))
              {
                  printf("%d\n", v.step + 1);
                  exit(0);
              }
                flag[tmp] = 1;
                queue_tail++;
                queue[queue_tail].step = v.step + 1;
                queue[queue_tail].x = tmp;
          }
      }

      queue_head ++;
  }

  printf("Impossible\n");
  return 0;
}
ACM, POJ

Comments