QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334351#7751. Palindrome PathCall_me_EricWA 1ms3856kbC++172.4kb2024-02-21 19:29:362024-02-21 19:29:36

Judging History

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

  • [2024-02-21 19:29:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3856kb
  • [2024-02-21 19:29:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 30 + 10;
char ch[maxn][maxn];
int n, m;
int sx, sy, tx, ty;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = { 0,-1, 1, 0};
const char opt[5] = {'U','L','R','D'};
int cnt;
bool vis[maxn][maxn];
void check(int x,int y){
    vis[x][y] = 1;cnt--;
    for(int i = 0;i < 4;i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || ny < 1 || nx > n || ny > m)continue;
        if(vis[nx][ny] || ch[nx][ny] == 0)continue;
        check(nx,ny);
    }
}
string ans = "";
void work(int k){
    for(int i = 1;;i++){
        if(ch[tx + dx[k] * i][ty + dy[k] * i] == 0){
            ans += string(i - 1,opt[k ^ 1]) + string(i,opt[k]);
            break;
        }
        if(ch[sx - dx[k] * i][sy - dy[k] * i] == 0){
            ans += string(i,opt[k ^ 1]) + string(i,opt[k]);
            break;
        }
    }
    sx += dx[k];sy += dy[k];
}
void solve(int k){
    vis[sx][sy] = 1;
    if(k && abs(sx - tx) + abs(sy - ty) < 2){
        cout << ans;
        if(sx == tx + 1)putchar('U');
        if(sx == tx - 1)putchar('D');
        if(sy == ty + 1)putchar('L');
        if(sy == ty - 1)putchar('R');
        reverse(ans.begin(),ans.end());
        cout << ans << "\n";exit(0);
    }
    for(int i = 0;i < 4;i++){
        int nx = sx + dx[i], ny = sy + dy[i];
        if(nx < 1 || ny < 1 || nx > n || ny > m)continue;
        if(ch[nx][ny] == 1 && !vis[nx][ny]){work(i);solve(k);work(i ^ 1);}
    }
}
void main(){
    n = read(); m = read();
    for(int i = 1;i <= n;i++){
        cin >> ch[i] + 1;
        for(int j = 1;j <= m;j++){ch[i][j] -= '0';cnt += ch[i][j] == 1;}
    }
    sx = read(); sy = read(); tx = read(); ty = read();
    check(sx,sy);if(cnt > 0){puts("-1");return;}
    memset(vis,0,sizeof(vis));solve(0);
    memset(vis,0,sizeof(vis));solve(1);
    return;
}
};
bool edmemory;
signed main(){
    auto stclock = clock();
    Call_me_Eric::main();
    auto edclock = clock();
    cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
    cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
    return 0;
}
/*
2 2
11
11
1 1 2 2
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3668kb

input:

2 2
11
11
1 1 2 2

output:

RDULLURDDRULLUDR

result:

ok Valid Solution (Length = 16).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:


result:

wrong answer (1,1) Not Visited