QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515386 | #2265. Short Coding | IllusionaryDominance# | WA | 0ms | 3688kb | C++14 | 5.0kb | 2024-08-11 17:30:51 | 2024-08-11 17:31:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
const int fx[4] = {1, 0, -1, 0};
const int fy[4] = {0, -1, 0, 1};
struct Code{
int op, gt;
}ans[N], now[N];
int flag, len = 1;
int us1[N], us3[N];
int n, m;
char s[N][N];
int vis[10000000];
int calc(int x, int y, int dir, int ln){return ((x - 1) * m + y) * 4 * len + (ln - 1) * 4 + dir;}
bool check(){
int x = 1, y, dir = 0, ln = 1;
for (y = 1; y <= m; ++ y) if(s[x][y] == 'S') break;
while(1){
// cout << x << " " << y << " " << dir << " " << ln << "\n";
if(s[x][y] == 'G') return 1;
if(vis[calc(x, y, dir, ln)]) break;
vis[calc(x, y, dir, ln)] = 1;
int dx = x + fx[dir], dy = y + fy[dir];
switch (now[ln].op)
{
case 1:
ln = now[ln].gt;
break;
case 2:
if(s[dx][dy] == '.' || s[dx][dy] == 'G' || s[dx][dy] == 'S') ln = now[ln].gt;
else ln = ln % len + 1;
break;
case 3:
if(s[dx][dy] == '.' || s[dx][dy] == 'G' || s[dx][dy] == 'S') x = dx, y = dy;
ln = ln % len + 1;
break;
case 4:
dir = (dir + 3) % 4;
ln = ln % len + 1;
break;
case 5:
dir = (dir + 1) % 4;
ln = ln % len + 1;
break;
}
}
x = 1, y, dir = 0, ln = 1;
for (y = 1; y <= m; ++ y) if(s[x][y] == 'S') break;
while(1){
if(s[x][y] == 'G') return 1;
if(vis[calc(x, y, dir, ln)] == 0) break;
vis[calc(x, y, dir, ln)] = 0;
int dx = x + fx[dir], dy = y + fy[dir];
switch (now[ln].op)
{
case 1:
ln = now[ln].gt;
break;
case 2:
if(s[dx][dy] == '.' || s[dx][dy] == 'G' || s[dx][dy] == 'S') ln = now[ln].gt;
else ln = ln % len + 1;
break;
case 3:
if(s[dx][dy] == '.' || s[dx][dy] == 'G' || s[dx][dy] == 'S') x = dx, y = dy;
ln = ln % len + 1;
break;
case 4:
dir = (dir + 3) % 4;
ln = ln % len + 1;
break;
case 5:
dir = (dir + 1) % 4;
ln = ln % len + 1;
break;
}
}
return 0;
}
void dfs(int o, int maxs){
if(o > maxs){
// for (int i = 1; i <= len; ++ i){
// switch (now[i].op)
// {
// case 1:
// cout << "GOTO " << now[i].gt << "\n";
// break;
// case 2:
// cout << "IF_OPEN " << now[i].gt << "\n";
// break;
// case 3:
// cout << "FORWARD\n";
// break;
// case 4:
// cout << "LEFT\n";
// break;
// case 5:
// cout << "RIGHT\n";
// break;
// }
// }
if(check()) flag = 1, memcpy(ans, now, sizeof(ans));
return;
}
for (int i = 1; i <= 5 && flag == 0; ++ i){
if(now[o - 1].op == 1 && i == 1) continue;
if(now[o - 1].op == 1 && i == 2) continue;
if(now[o - 1].op == 2 && i == 2) continue;
if(us1[o] && i == 1) continue;
if(us3[o] && (i == 1 || i == 2)) continue;
now[o].op = i;
if(i == 1){
for (int j = 1; j <= maxs; ++ j){
if(i == j) continue;
if(j < i && now[i].op == 1) continue;
++ us1[j]; now[o].gt = j;
dfs(o + 1, maxs);
-- us1[j];
}
continue;
}
if(i == 2){
for (int j = 1; j <= maxs; ++ j){
if(i == j) continue;
if(j < i && (now[i].op == 1 || now[i].op == 2)) continue;
++ us3[j]; now[o].gt = j;
dfs(o + 1, maxs);
-- us3[j];
}
continue;
}
dfs(o + 1, maxs);
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++ i) cin >> s[i] + 1;
while(1){
dfs(1, len);
if(flag) break;
++ len;
}
cout << len << "\n";
for (int i = 1; i <= len; ++ i){
switch (ans[i].op)
{
case 1:
cout << "GOTO " << ans[i].gt << "\n";
break;
case 2:
cout << "IF-OPEN " << ans[i].gt << "\n";
break;
case 3:
cout << "FORWARD\n";
break;
case 4:
cout << "LEFT\n";
break;
case 5:
cout << "RIGHT\n";
break;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
4 2 S# .# .# G.
output:
1 FORWARD
result:
ok correct answer!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 6 ##S..# #..##. .G..#.
output:
2 FORWARD RIGHT
result:
ok correct answer!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 7 ....S## .#.#... ##.#.G#
output:
2 FORWARD LEFT
result:
ok correct answer!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 8 ...S.#.# ##..#.#. ###...#. #.#.#G.#
output:
3 FORWARD FORWARD LEFT
result:
ok correct answer!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
3 5 .S#.. ..... ..#G.
output:
3 FORWARD LEFT FORWARD
result:
ok correct answer!
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3652kb
input:
10 10 .....S#... ...#...... ....##.... .#.....#.. ....#..... ..#....... ...#...... .......... .#...#.... G.#..#...#
output:
4 GOTO 2 LEFT FORWARD IF-OPEN 3
result:
wrong answer wrong answer. the length of your program is 3 but the optimal one is 4.