QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18332 | #2265. Short Coding | linmuhan# | WA | 8ms | 3840kb | C++14 | 3.5kb | 2022-01-17 21:21:23 | 2022-05-04 17:58:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 12;
const int dx[5][2] = {{0, 0}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int n, m, Ans = 5;
int xs, ys, xt, yt;
string dic[N * 2] = {"LEFT", "RIGHT", "IF_OPEN 1", "IF_OPEN 2", "IF_OPEN 3"
, "IF_OPEN 4", "GOTO 1", "GOTO 2", "GOTO 3", "GOTO 4", "FORWARD"};
string opt[N * 2], ans[N * 2];
char s[N][N];
bool f[N][N][N][N], Flag, BUHEFA;
bool valid (int x, int y) {return (x >= 1 && x <= n && y >= 1 && y <= m && s[x][y] != '#');}
void dfss (int x, int y, int stp, int dir, int lim) {
if (Flag) return ;
if (stp == lim + 1) stp = 1;
if (x == xt && y == yt) {
Flag = 1;
return ;
}
if (f[x][y][stp][dir]) {
BUHEFA = 1;
return ;
}
f[x][y][stp][dir] = 1;
if (opt[stp] == "LEFT") {
dir --;
if (dir == 0) dir = 4;
dfss (x, y, stp + 1, dir, lim);
}
if (opt[stp] == "RIGHT") {
dir ++;
if (dir == 5) dir = 1;
dfss (x, y, stp + 1, dir, lim);
}
if (opt[stp] == "GOTO 1") {
if (lim >= 1) {
dfss (x, y, 1, dir, lim);
} else {
BUHEFA = 1;
}
}
if (opt[stp] == "GOTO 2") {
if (lim >= 2) {
dfss (x, y, 2, dir, lim);
} else {
BUHEFA = 1;
}
}
if (opt[stp] == "GOTO 3") {
if (lim >= 3) {
dfss (x, y, 3, dir, lim);
} else {
BUHEFA = 1;
}
}
if (opt[stp] == "GOTO 4") {
if (lim >= 4) {
dfss (x, y, 4, dir, lim);
} else {
BUHEFA = 1;
}
}
if (opt[stp] == "IF_OPEN 1") {
int xx = x + dx[dir][0], yy = y + dx[dir][1];
if (valid (xx, yy)) {
if (lim >= 1) {
dfss (x, y, 1, dir, lim);
} else {
BUHEFA = 1;
}
} else {
dfss (x, y, stp + 1, dir, lim);
}
}
if (opt[stp] == "IF_OPEN 2") {
int xx = x + dx[dir][0], yy = y + dx[dir][1];
if (valid (xx, yy)) {
if (lim >= 2) {
dfss (x, y, 2, dir, lim);
} else {
BUHEFA = 1;
}
} else {
dfss (x, y, stp + 1, dir, lim);
}
}
if (opt[stp] == "IF_OPEN 3") {
int xx = x + dx[dir][0], yy = y + dx[dir][1];
if (valid (xx, yy)) {
if (lim >= 3) {
dfss (x, y, 3, dir, lim);
} else {
BUHEFA = 1;
}
} else {
dfss (x, y, stp + 1, dir, lim);
}
}
if (opt[stp] == "IF_OPEN 4") {
int xx = x + dx[dir][0], yy = y + dx[dir][1];
if (valid (xx, yy)) {
if (lim >= 4) {
dfss (x, y, 4, dir, lim);
} else {
BUHEFA = 1;
}
} else {
dfss (x, y, stp + 1, dir, lim);
}
}
if (opt[stp] == "FORWARD") {
int xx = x + dx[dir][0], yy = y + dx[dir][1];
if (valid (xx, yy)) {
dfss (xx, yy, stp + 1, dir, lim);
} else {
dfss (x, y, stp + 1, dir, lim);
}
}
}
bool chk (int len) {
if (len == 4 && opt[1] == "RIGHT" && opt[2] == "RIGHT" && opt[3] == "FORWARD" && opt[4] == "GOTO 2") {
len ++;
len --;
}
memset (f, 0, sizeof f);
Flag = 0; BUHEFA = 0;
dfss (xs, ys, 1, 3, len);
return Flag && (! BUHEFA);
}
void dfs (int dep) {
if (dep > 5) return ;
if (dep > Ans) return ;
if (chk (dep - 1)) {
if (Ans > dep - 1) {
Ans = dep - 1;
for (int i=1;i<=dep-1;i++) ans[i] = opt[i];
}
}
for (int i=0;i<11;i++) {
opt[dep] = dic[i];
dfs (dep + 1);
}
}
int main () {
cin >> n >> m;
for (int i=1;i<=n;i++) scanf ("%s", (s[i] + 1));
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (s[i][j] == 'S') xs = i, ys = j;
if (s[i][j] == 'G') xt = i, yt = j;
}
}
dfs (1);
if (Ans < 5) {
cout << Ans << endl;
for (int i=1;i<=Ans;i++) cout << ans[i] << endl;
return 0;
}
puts ("5");
puts ("LEFT");
puts ("IF_OPEN 5");
puts ("RIGHT");
puts ("GOTO 2");
puts ("FORWARD");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3776kb
input:
4 2 S# .# .# G.
output:
1 FORWARD
result:
ok correct answer!
Test #2:
score: 0
Accepted
time: 3ms
memory: 3644kb
input:
3 6 ##S..# #..##. .G..#.
output:
2 FORWARD RIGHT
result:
ok correct answer!
Test #3:
score: 0
Accepted
time: 3ms
memory: 3732kb
input:
3 7 ....S## .#.#... ##.#.G#
output:
2 FORWARD LEFT
result:
ok correct answer!
Test #4:
score: 0
Accepted
time: 8ms
memory: 3708kb
input:
4 8 ...S.#.# ##..#.#. ###...#. #.#.#G.#
output:
3 FORWARD FORWARD LEFT
result:
ok correct answer!
Test #5:
score: 0
Accepted
time: 3ms
memory: 3840kb
input:
3 5 .S#.. ..... ..#G.
output:
3 FORWARD LEFT FORWARD
result:
ok correct answer!
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3704kb
input:
10 10 .....S#... ...#...... ....##.... .#.....#.. ....#..... ..#....... ...#...... .......... .#...#.... G.#..#...#
output:
3 LEFT FORWARD IF_OPEN 2
result:
wrong answer unauthorized token IF_OPEN