[20220115专题选讲]Short Coding

Posted on | In

一道奇怪的模拟题。

大意

给定一个 $n\times m$ 的网格，有些格子无法到达。有一个机器人从第一行某处出发，一开始面向正下，目标达到最后一行某处（保证可达），它会重复执行一段由五种语句构成的代码，分别是：

代码格式 含义
FORWARD 向前一格，如果面前无法到达或为边界则忽略此语句
LEFT 左转
RIGHT 右转
GOTO x 跳转到第 $x$ 行继续进行
IF-OPEN x 如果当前可以进行 FORWARD 操作，则跳转到第 $x$ 行，否则到下一行

输入网格，输出行数最少的代码。（多解任意输出）

$n,m\in[1,10]$。

时限 2s。

source: ICPC Asia Regional Contest, Yokohama, 2021–03–17; Problem C

link: http://qoj.ac/contest/802/problem/2265

思路

首先注意到迷宫通解：摸墙。容易写出以下的通解代码：

1
2
3
4
5
LEFT
IF-OPEN 5
RIGHT
GOTO 2
FORWARD

（注意起点、终点一定在墙边）

考察行数 $\le 4$ 的代码，发现长度为 $4$ 的代码都仅有 $9^4=6561$ 种，非常小。

枚举代码，暴力计算直到重复。单次状态数为 $4\times4\times10\times10=1600$，完全可以接受。

时间复杂度 $\Theta(nm)$。

代码

懒得打 dfs 了，无脑复制粘贴多好（

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <cstdio>
#include <algorithm>
#include <cstring>

namespace mirai {

bool maze[15][15];
int prog[4];
bool vst[15][15][4][4];
char str[11][10] = {"GOTO 4", "GOTO 3", "GOTO 2", "GOTO 1", "LEFT", "FORWARD", "RIGHT", "IF-OPEN 1", "IF-OPEN 2", "IF-OPEN 3", "IF-OPEN 4"};

int main(int argc, char** argv) {
  int n, m;
  std::scanf("%d%d", &n, &m);
  std::memset(maze, 0x01, sizeof(maze));
  int y1, y2;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      char ch;
      std::scanf(" %c", &ch);
      maze[i][j] = (ch == '#');
      if (ch == 'S') {
        y1 = j;
      }
      if (ch == 'G') {
        y2 = j;
      }
    }
  }
  
  int len;
  int move[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  auto halt = [&](int len2) -> bool {
//    std::printf("halt(%d)\n", len2);
    std::memset(vst, 0x00, sizeof(vst));
    int x = 1, y = y1, l = 0, f = 2;
    while (true) {
      if (x == n && y == y2) { return true; }
      if (vst[x][y][l][f]) { return false; }
      vst[x][y][l][f] = true;
      int ord = std::abs(prog[l]), open = !maze[x + move[f][0]][y + move[f][1]];
//      std::printf(" %d %d %d %d %d %d\n", x, y, l, f, ord, open);
      if (ord == 0) {
        if (open) {
          x += move[f][0];
          y += move[f][1];
        }
        l = (l + 1) % len2;
      } else if (ord == 1) {
        f = (f + prog[l]) & 3;
        l = (l + 1) % len2;
      } else {
        if (open || prog[l] < 0) {
          l = ord - 2;
        } else {
          l = (l + 1) % len2;
        }
      }
    }
  };
  
  len = 1;
  for (prog[0] = -5; prog[0] <= 5; ++prog[0]) {
    int ord = std::abs(prog[0]);
    if (ord == 2 || ord >= len + 2) { continue; }
    if (halt(len)) {
      std::printf("%d\n", len);
      for (int i = 0; i < len; ++i) {
        std::puts(str[prog[i] + 5]);
      }
      return 0;
    }
  }
  
  len = 2;
  for (prog[0] = -5; prog[0] <= 5; ++prog[0]) {
    int ord = std::abs(prog[0]);
    if (ord == 2 || ord >= len + 2) { continue; }
    for (prog[1] = -5; prog[1] <= 5; ++prog[1]) {
      int ord = std::abs(prog[1]);
      if (ord == 3 || ord >= len + 2) { continue; }
      if (halt(len)) {
        std::printf("%d\n", len);
        for (int i = 0; i < len; ++i) {
          std::puts(str[prog[i] + 5]);
        }
        return 0;
      }
    }
  }
  
  len = 3;
  for (prog[0] = -5; prog[0] <= 5; ++prog[0]) {
    int ord = std::abs(prog[0]);
    if (ord == 2 || ord >= len + 2) { continue; }
    for (prog[1] = -5; prog[1] <= 5; ++prog[1]) {
      int ord = std::abs(prog[1]);
      if (ord == 3 || ord >= len + 2) { continue; }
      for (prog[2] = -5; prog[2] <= 5; ++prog[2]) {
        int ord = std::abs(prog[2]);
        if (ord == 4 || ord >= len + 2) { continue; }
        if (halt(len)) {
          std::printf("%d\n", len);
          for (int i = 0; i < len; ++i) {
            std::puts(str[prog[i] + 5]);
          }
          return 0;
        }
      }
    }
  }
  
  len = 4;
  for (prog[0] = -5; prog[0] <= 5; ++prog[0]) {
    int ord = std::abs(prog[0]);
    if (ord == 2 || ord >= len + 2) { continue; }
    for (prog[1] = -5; prog[1] <= 5; ++prog[1]) {
      int ord = std::abs(prog[1]);
      if (ord == 3 || ord >= len + 2) { continue; }
      for (prog[2] = -5; prog[2] <= 5; ++prog[2]) {
        int ord = std::abs(prog[2]);
        if (ord == 4 || ord >= len + 2) { continue; }
        for (prog[3] = -5; prog[3] <= 5; ++prog[3]) {
          int ord = std::abs(prog[3]);
          if (ord == 5 || ord >= len + 2) { continue; }
          if (halt(len)) {
            std::printf("%d\n", len);
            for (int i = 0; i < len; ++i) {
              std::puts(str[prog[i] + 5]);
            }
            return 0;
          }
        }
      }
    }
  }
  
  std::puts("5");
  std::puts("LEFT");
  std::puts("IF-OPEN 5");
  std::puts("RIGHT");
  std::puts("GOTO 2");
  std::puts("FORWARD");
      
  return 0;
}

}

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}