QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#515370#2265. Short CodingIllusionaryDominance#WA 0ms3712kbC++145.2kb2024-08-11 17:23:472024-08-11 17:23:48

Judging History

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

  • [2024-08-11 17:23:48]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3712kb
  • [2024-08-11 17:23:47]
  • 提交

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 == 4 && i == 5) continue;
        if(now[o - 1].op == 5 && i == 4) continue;
        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;
            
        }
    }
}

詳細信息

Test #1:

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

input:

4 2
S#
.#
.#
G.

output:

1
FORWARD

result:

ok correct answer!

Test #2:

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

input:

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

output:

2
FORWARD
RIGHT

result:

ok correct answer!

Test #3:

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

input:

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

output:

2
FORWARD
LEFT

result:

ok correct answer!

Test #4:

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

input:

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

output:

3
FORWARD
FORWARD
LEFT

result:

ok correct answer!

Test #5:

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

input:

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

output:

3
FORWARD
LEFT
FORWARD

result:

ok correct answer!

Test #6:

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

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.