QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515461#2265. Short CodingCheek_support#WA 0ms3844kbC++203.8kb2024-08-11 17:56:172024-08-11 17:56:17

Judging History

你现在查看的是最新测评结果

  • [2024-08-11 17:56:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3844kb
  • [2024-08-11 17:56:17]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define DEBUG_VAR(x) { cerr << "* "#x" = " << x << endl; }
#define DEBUG_ARR(arr, l, r) { \
    cerr << "* "#arr"[" << l << ", " << r << "]:"; \
    for(auto it = l, itr = r; it <= itr; it++) \
        cerr << arr[it] << ", "; \
    cerr << endl; \
}
#define DEBUG_FMT(...) { cerr << "* "; fprintf(stderr, __VA_ARGS__); }
#define DEBUG_HERE { DEBUG_FMT("Passing [%s] in LINE %d\n", __FUNCTION__, __LINE__); } 

using namespace std;
using LL = long long;
using ULL = unsigned long long;

const int N = 1024, M = 11;
const int LEN = 21;

int n, m;
char a[N][N];

struct Command
{
    int type; 
    int l;
};

Command c[LEN];

bool vis[11][11][4][LEN];

const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; // -> right

int sx, sy;

void print(int len)
{
    cout << len << endl;
    for(int i = 1; i <= len; i++) {
        if(c[i].type == 1) {
            cout << "GOTO " << c[i].l << endl;
        } else if(c[i].type == 2) {
            cout << "IF-OPEN " << c[i].l << endl; 
        } else if(c[i].type == 3) {
            cout << "FORWARD" << endl;
        } else if(c[i].type == 4) {
            cout << "LEFT" << endl;
        } else {
            cout << "RIGHT" << endl;
        }
    }
}

void check(int len)
{
    memset(vis, 0, sizeof vis);

    int pc = 1;
    int x = sx, y = sy;
    int d = 2;

    while(true) {
        if(vis[x][y][d][pc]) return;
        vis[x][y][d][pc] = true;

        if(a[x][y] == 'G') break;

        Command com = c[pc];
        if(com.type == 1) { // GOTO
            pc = com.l;
        } else if(com.type == 2) { // IF-OPEN
            int nx = x + dx[d], ny = y + dy[d];
            bool is_open = true;
            if(nx < 1 || nx > n || ny < 1 || ny > m) {
                is_open = false;
            } else if(a[nx][ny] == '#') {
                is_open = false;
            }
            if(is_open) {
                pc = com.l;
            } else {
                if(pc == len) pc = 1;
                else pc++;
            }
        } else if(com.type == 3) { // FORWARD
            int nx = x + dx[d], ny = y + dy[d];
            bool is_open = true;
            if(nx < 1 || nx > n || ny < 1 || ny > m) {
                is_open = false;
            } else if(a[nx][ny] == '#') {
                is_open = false;
            }
            if(is_open) {
                x = nx, y = ny;
            }
            if(pc == len) pc = 1;
            else pc++;
        } else if(com.type == 4) { // LEFT
            d = (d + 4 - 1)%4;
            if(pc == len) pc = 1;
            else pc++;
        } else {
            d = (d + 1)%4;
            if(pc == len) pc = 1;
            else pc++;
        }
    }

    print(len);
    exit(0);
}

void dfs(int step, int max_step) 
{
    if(step > max_step) {
        check(max_step);
        return;
    }

    for(int i = 1; i <= 5; i++) {
        c[step].type = i;
        if(i == 1 || i == 2) {
            for(int j = 1; j <= max_step; j++) {
                if(j == step) continue;
                c[step].l = j;
            }
        }
        dfs(step + 1, max_step);
    }
}

int main()
{
    // freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%s", a[i] + 1);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == 'S') {
                sx = i, sy = j;
            }
        }
    }

    for(int i = 1; i < 5; i++) {
        dfs(1, i);
    }
    // assert(false);
    c[1].type = 4;
    c[2].type = 2; c[2].l = 5;
    c[3].type = 5;
    c[4].type = 1; c[4].l = 2;
    c[5].type = 3;
    print(5);
    // check(5);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3760kb

input:

4 2
S#
.#
.#
G.

output:

1
FORWARD

result:

ok correct answer!

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

3 6
##S..#
#..##.
.G..#.

output:

2
FORWARD
RIGHT

result:

ok correct answer!

Test #3:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

3 7
....S##
.#.#...
##.#.G#

output:

2
FORWARD
LEFT

result:

ok correct answer!

Test #4:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

4 8
...S.#.#
##..#.#.
###...#.
#.#.#G.#

output:

3
FORWARD
FORWARD
LEFT

result:

ok correct answer!

Test #5:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

3 5
.S#..
.....
..#G.

output:

3
FORWARD
LEFT
FORWARD

result:

ok correct answer!

Test #6:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

10 10
.....S#...
...#......
....##....
.#.....#..
....#.....
..#.......
...#......
..........
.#...#....
G.#..#...#

output:

3
LEFT
FORWARD
IF-OPEN 2

result:

ok correct answer!

Test #7:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

7 9
.##S.#..#
.........
.........
...#...##
###..####
........#
.....##G#

output:

3
RIGHT
FORWARD
IF-OPEN 2

result:

ok correct answer!

Test #8:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

3 9
..#.#.#S#
#...#...#
.G....#.#

output:

3
FORWARD
RIGHT
FORWARD

result:

ok correct answer!

Test #9:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

4 5
#S...
..#..
.#..#
.#.G#

output:

3
RIGHT
FORWARD
FORWARD

result:

ok correct answer!

Test #10:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

6 8
..S..#.#
...#...#
....#..#
#.#.##..
.......#
.#..#G.#

output:

4
FORWARD
LEFT
FORWARD
RIGHT

result:

ok correct answer!

Test #11:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

9 10
S.........
.#..#....#
........#.
..........
.....#.#..
.#...#....
#..#.##.#.
..#..#...#
..#.#....G

output:

4
LEFT
FORWARD
RIGHT
FORWARD

result:

ok correct answer!

Test #12:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

10 4
#.S.
.#.#
##.#
##..
.#..
#...
#.##
..#.
.#..
G.##

output:

4
FORWARD
RIGHT
FORWARD
LEFT

result:

ok correct answer!

Test #13:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

9 9
#..#...S#
.#...##.#
.....##..
..#..#...
..#..#..#
.#..#.#.#
.###.....
..#.#.##.
G#....#.#

output:

4
RIGHT
FORWARD
LEFT
FORWARD

result:

ok correct answer!

Test #14:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

7 3
.S#
#..
..#
...
..#
.#.
.G.

output:

4
FORWARD
FORWARD
FORWARD
LEFT

result:

ok correct answer!

Test #15:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

6 6
..#S..
#.#.#.
.....#
#.#...
..#...
..G##.

output:

4
FORWARD
FORWARD
LEFT
FORWARD

result:

ok correct answer!

Test #16:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

6 8
....#S..
......#.
..##..#.
###.#.##
..#...#.
##.G#..#

output:

4
FORWARD
FORWARD
RIGHT
FORWARD

result:

ok correct answer!

Test #17:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

10 8
#..S.###
.#....##
.#......
....#.#.
#...#..#
........
....#.##
...#.###
.#.#...#
.#...G.#

output:

4
FORWARD
LEFT
FORWARD
IF-OPEN 3

result:

ok correct answer!

Test #18:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

7 6
...##S
#.....
....#.
...#.#
....#.
#.....
.....G

output:

4
FORWARD
RIGHT
FORWARD
IF-OPEN 3

result:

ok correct answer!

Test #19:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

4 8
.##..S..
#.###..#
.#...#..
...#G...

output:

4
RIGHT
FORWARD
FORWARD
FORWARD

result:

ok correct answer!

Test #20:

score: -100
Wrong Answer
time: 0ms
memory: 3744kb

input:

3 10
##.......S
####.####.
...#..G##.

output:

5
LEFT
IF-OPEN 5
RIGHT
GOTO 2
FORWARD

result:

wrong answer wrong answer. the length of your program is 4 but the optimal one is 5.