QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94584 | #2265. Short Coding | whatever# | WA | 0ms | 3684kb | C++23 | 2.4kb | 2023-04-06 18:45:44 | 2023-04-06 18:45:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 12;
int n, m, ans, use[N][N];
string str[N];
struct oper {
int type;
int l;
}a[N];
constexpr int D[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
int sx, sy, tx, ty;
bool check() {
int x = sx, y = sy, dir = 3, pc = 1;
static int vis[N][N][4][N], ts;
ts ++;
while(vis[x][y][dir][pc] != ts) {
vis[x][y][dir][pc] = ts;
if(a[pc].type == 1) {
pc = a[pc].l;
}
else if(a[pc].type == 2) {
int dx = x + D[dir][0], dy = y + D[dir][1];
if(use[dx][dy]) {
pc = a[pc].l;
} else {
pc = pc % ans + 1;
}
}
else if(a[pc].type == 3) {
int dx = x + D[dir][0], dy = y + D[dir][1];
if(use[dx][dy]) {
x = dx, y = dy;
}
pc = pc % ans + 1;
}
else if(a[pc].type == 4) {
dir = (dir + 1) % 4;
pc = pc % ans + 1;
}
else if(a[pc].type == 5) {
dir = (dir + 3) % 4;
pc = pc % ans + 1;
}
if(x == tx && y == ty) return true;
}
// cout << "-------\n";
return false;
}
bool dfs(int i) {
if(i == ans + 1) {
return check();
}
for(int u = 1; u <= ans; u ++) {
a[i].type = 1;
a[i].l = u;
if(dfs(i + 1)) return true;
}
for(int u = 1; u <= ans; u ++) {
a[i].type = 2;
a[i].l = u;
if(dfs(i + 1)) return true;
}
for(int u = 3; u <= 5; u ++) {
a[i].type = u;
if(dfs(i + 1)) return true;
}
return false;
}
int main() {
freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
cin >> str[i];
str[i] = "#" + str[i];
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
use[i][j] = str[i][j] != '#';
if(str[i][j] == 'S') sx = i, sy = j;
if(str[i][j] == 'G') tx = i, ty = j;
}
}
for(ans = 1; ; ans ++) {
if(ans == 5) {
cout << "5\n";
cout << "LEFT\n";
cout << "IF-OPEN 5\n";
cout << "RIGHT\n";
cout << "GOTO 2\n";
cout << "FORWARD\n";
exit(0);
}
if(dfs(1)) {
cout << ans << '\n';
for(int i = 1; i <= ans; i ++) {
if(a[i].type == 1) {
cout << "GOTO " << a[i].l << '\n';
} else if(a[i].type == 2) {
cout << "IF-OPEN " << a[i].l << '\n';
} else if(a[i].type == 3) {
cout << "FORWARD\n";
} else if(a[i].type == 4) {
cout << "LEFT\n";
} else if(a[i].type == 5) {
cout << "RIGHT\n";
}
}
exit(0);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3684kb
input:
4 2 S# .# .# G.
output:
1 GOTO 1
result:
wrong answer your program is not correct.