QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#339233 | #7751. Palindrome Path | sinsop90 | TL | 0ms | 0kb | C++14 | 1.7kb | 2024-02-26 21:37:16 | 2024-02-26 21:37:16 |
answer
#include <bits/stdc++.h>
using namespace std;
int fx[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}, n, m, sx, sy, ex, ey, vis[35][35];
char s[35][35];
vector<int> ans;
struct node {
int x, y;
};
vector<node> vec;
bool check(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m && s[x][y] == '1';
}
int getans(int x, int y, int op) {
int st = 0, X = ex, Y = ey;
x += fx[op ^ 2][0], y += fx[op ^ 2][1];
X += fx[op][0], y += fx[op][1];
for(;check(x, y) && check(X, Y);) {
ans.push_back(op ^ 2);
x += fx[op ^ 2][0], y += fx[op ^ 2][1];
X += fx[op][0], Y += fx[op][1];
st ++;
}
if(!check(x, y) && check(X, Y)) ans.push_back(op ^ 2);
for(int i = 1;i <= st + 1;i++) ans.push_back(op);
}
int dfs(int x, int y) {
vis[x][y] = 1;
int flagn = 0;
for(int i = 0;i <= 3;i++) {
int xx = x + fx[i][0], yy = y + fx[i][1];
if(vis[xx][yy] || !check(xx, yy)) continue;
getans(x, y, i);
int flag = dfs(xx, yy);
if(flag) vec.push_back({x, y});
flagn |= flag;
getans(xx, yy, i ^ 2);
}
if(x == ex && y == ey) vec.push_back({x, y}), flagn = 1;
return flagn;
}
void print() {
for(int x : ans) {
if(x == 0) cout << "R";
else if(x == 1) cout << "D";
else if(x == 2) cout << "L";
else cout << "U";
}
}
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;
cin >> sx >> sy >> ex >> ey;
dfs(sx, sy);
reverse(vec.begin(), vec.end());
for(int i = 0;i < (int)vec.size() - 1;i++) {
int x = vec[i].x, y = vec[i].y;
for(int j = 0;j <= 3;j++) {
int xx = x + fx[i][0], yy = y + fx[i][1];
if(xx == vec[i + 1].x && yy == vec[i + 1].y) getans(x, y, j);
}
}
print();
reverse(ans.begin(), ans.end());
print();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
2 2 11 11 1 1 2 2