QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515442#2265. Short CodingCheek_support#WA 0ms3816kbC++203.8kb2024-08-11 17:50:172024-08-11 17:50:17

Judging History

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

  • [2024-08-11 17:50:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3816kb
  • [2024-08-11 17:50: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;

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

struct Command
{
    int type; 
    int l;
};

Command c[N], ans[N];

bool vis[11][11][4][10];

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++) {
                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);
    }

    // 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: 3632kb

input:

4 2
S#
.#
.#
G.

output:

1
FORWARD

result:

ok correct answer!

Test #2:

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

input:

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

output:

2
FORWARD
RIGHT

result:

ok correct answer!

Test #3:

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

input:

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

output:

2
FORWARD
LEFT

result:

ok correct answer!

Test #4:

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

input:

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

output:

3
FORWARD
FORWARD
LEFT

result:

ok correct answer!

Test #5:

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

input:

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

output:

3
FORWARD
LEFT
FORWARD

result:

ok correct answer!

Test #6:

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

input:

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

output:

4
LEFT
FORWARD
FORWARD
FORWARD

result:

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