QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#479226#7751. Palindrome Pathucup-team052#WA 13ms64564kbC++143.6kb2024-07-15 16:01:292024-07-15 16:01:29

Judging History

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

  • [2024-07-15 16:01:29]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:64564kb
  • [2024-07-15 16:01:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const char dc[4] = {'D', 'U', 'R', 'L'};

const int N = 905;

struct atom {
	int x, y, d;
	atom (int a = 0, int b = 0, int c = 0) : x(a), y(b), d(c) {}
};

char c[35][35];
queue < pair <int, int> > q;
vector <atom> adj[N][N], radj[N][N];
vector <int> ans;
int frx[N][N], fry[N][N], fr[N][N], vis[N][N];
int frx2[N][N], fry2[N][N], fr2[N][N], vis2[N][N], vis3[N][N];
int n, m, sx, sy, tx, ty;

inline int s(int x, int y) { return (x - 1) * m + y; }

int seq[N * N], len;
void solve(int x, int y) {
	if (!frx[x][y]) return;
	solve(frx[x][y], fry[x][y]);
	seq[++len] = fr[x][y];
}

void solve2(int x, int y) {
	if (!frx2[x][y]) return;
	seq[++len] = fr2[x][y];
	solve2(frx2[x][y], fry2[x][y]);
}

void go(int &x, int &y, int d) {
	int tx = x + dx[d], ty = y + dy[d];
	if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && c[tx][ty] == '1') x = tx, y = ty;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%s", c[i] + 1);
	scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
	q.push(make_pair(s(sx, sy), s(tx, ty))); vis[s(sx, sy)][s(tx, ty)] = 1;
	while (!q.empty()) {
		pair <int, int> t = q.front(); q.pop();
		int ux1 = (t.first - 1) / m + 1, uy1 = (t.first - 1) % m + 1;
		int ux2 = (t.second - 1) / m + 1, uy2 = (t.second - 1) % m + 1;
		for (int d = 0; d < 4; d++) {
			for (int i = 0; i <= 1; i++) {
				int x1, y1, x2, y2;
				x1 = ux1 + dx[d]; y1 = uy1 + dy[d];
				if (x1 < 1 || x1 > n || y1 < 1 || y1 > m || c[x1][y1] == '0') x1 = ux1, y1 = uy1;
				if (i) {
					x2 = ux2 + dx[d ^ 1], y2 = uy2 + dy[d ^ 1];
					if (x2 < 1 || x2 > n || y2 < 1 || y2 > m || c[x2][y2] == '0') continue;
				} else {
					x2 = ux2 + dx[d], y2 = uy2 + dy[d];
					if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && c[x2][y2] == '1') continue;
					x2 = ux2; y2 = uy2;
				}
				int t1 = s(x1, y1), t2 = s(x2, y2);
				adj[t.first][t.second].push_back(atom(t1, t2, d));
				radj[t1][t2].push_back(atom(t.first, t.second, d));
				if (vis[t1][t2]) continue;
				vis[t1][t2] = 1; frx[t1][t2] = t.first; fry[t1][t2] = t.second; fr[t1][t2] = d; q.push(make_pair(t1, t2));
			}
		}
	}
	q.push(make_pair(s(sx, sy), s(tx, ty))); vis2[s(sx, sy)][s(tx, ty)] = 1;
	while (!q.empty()) {
		pair <int, int> t = q.front(); q.pop();
		for (auto v : radj[t.first][t.second]) {
			int t1 = v.x, t2 = v.y;
			if (vis2[t1][t2]) continue;
			vis2[t1][t2] = 1; frx2[t1][t2] = t.first; fry2[t1][t2] = t.second; fr2[t1][t2] = v.d; q.push(make_pair(t1, t2));
		}
	}
	vis3[sx][sy] = 1;
	int nx = sx, ny = sy;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (c[i][j] == '0' || vis3[i][j]) continue;
			int tt = s(i, j);
			for (int k = 1; k <= n * m; k++) {
				if (vis[tt][k] && vis2[tt][k]) {
					len = 0;
					solve(tt, k); solve2(tt, k);
					for (int t = 1; t <= len; t++) {
						ans.push_back(seq[t]);
						go(nx, ny, seq[t]); vis3[nx][ny] = 1;
					}
					assert(nx == sx && ny == sy);
					break;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int t = s(i, j);
			if (vis[t][t]) {
				solve(t, t);
				for (int k = 1; k <= len; k++) ans.push_back(seq[k]);
				for (auto i : ans) printf("%c", dc[i]), go(nx, ny, i);
				reverse(ans.begin(), ans.end());
				for (auto i : ans) printf("%c", dc[i]), go(nx, ny, i);
				assert(nx == tx && ny == ty);
				// for (int k = len; k >= 1; k--) printf("%c", dc[seq[k]]);
				return 0;
			}

		}
	}
	printf("-1\n");
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 9ms
memory: 61648kb

input:

2 2
11
11
1 1 2 2

output:

DURULDRLUDRLUDURLLRUDULRDULRDLURUD

result:

ok Valid Solution (Length = 34).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 3ms
memory: 49236kb

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

score: 0
Accepted
time: 4ms
memory: 64564kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

DDDUUUURLLUUUUDDLLRDDDDUUUULLRRRLUUUUDDLDDDDUUULLRRRLUUUUDDLDDDDUULLRRRLUUUUDDLDDDDURLLUUUUDDLLRDDDDULLRRRLUUUUDDLDDDDRLLUUUUDDLLRDDDDLLRRRLUUUUDDLDDDDLLRRRLUUUUDDLDDDDUUUURLLLLRUUUUDDDDLDDUUUULRRRLLDDDDLDDUUUULRRRLLDDDDRLLDDUUUULLRDDDDLDDUUUULRRRLLUDDDDRLLDDUUUULLRUDDDDLDDUUUULRRRLLUUDDDDLDDUUUULRR...

result:

ok Valid Solution (Length = 350).

Test #5:

score: 0
Accepted
time: 7ms
memory: 64316kb

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

DDDDRRRRLLLLLLLLRRRUUUUDDDLLLDRRRRLLLLURRRUUUDDDLDRRRRLLLLURUUUDDDDRDRRRLLLULUUUUDLDRRRRDLDLUULLLLRRRUUDDRRDDRRLLULLLURUUUDLDDLLDRRRRLLLLURRUURUDLDDDRRRRLLLLUUURUDDRDRDDRRLLUULULUURRDDDDRRLLLLUULLLLRRUURRRDDDDRRLLLLUULLLLRRUURDDDDRRRRLLLLLLLLRRRRDDDDRUURRLLLLUULLLLRRDDDDRRRUURRLLLLUULLLLRRDDDDRRUULU...

result:

ok Valid Solution (Length = 476).

Test #6:

score: 0
Accepted
time: 4ms
memory: 61948kb

input:

5 3
111
100
111
001
111
4 3 3 2

output:

URLDDLUUUUDDLLRRDURLDDLUURUULDDLRRDURLLUURDRDLUULDDLRRDRDDLLURRULRDDLLURRULURLDDLUUUULDDLRULURRULLDDRLURRULLDDRDRRLDDLUULDRDRUULLRUDRRLDDLUURUULDDLRUDRRLLDDUUUULDDLRU

result:

ok Valid Solution (Length = 166).

Test #7:

score: 0
Accepted
time: 3ms
memory: 64188kb

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

LUUDRUDRRUUUUDDLLUUDLURUDRUDULUUDRUDRULLUUDRUUDDUULUUDRUUDDUULULUULULUUDDUURDUULUUDDUURDUULLURDURDUULUDURDURULDUULLDDUUUURRDURDUUL

result:

ok Valid Solution (Length = 130).

Test #8:

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

input:

5 3
101
111
100
111
100
4 1 2 2

output:

UUURDUULDDDUURDRUUDLULDDRDULRDRLULDRDULDRDULUUURDUUDRUUULUDRDLUDRDLULRDRLUDRDDLULDUURDRUUDDDLUUDRUUU

result:

ok Valid Solution (Length = 100).

Test #9:

score: 0
Accepted
time: 3ms
memory: 64060kb

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

DLDUULDDRLLUURUUDRDDLULDDUURLUURUUDRDLDLLDDUUURLUUDRURRUDLDLDDURDLUURURRUDDLLDDRLUURUUDRDLDLDDRLUURUUDRDLDLDDRLUURUUDRDLDUULDDRLLRDDLUUDLDRDUURUULRDDLDLDRDUURUULRDDLDLDRDUURUULRDDLLDDURRURUULDRUDDLDLDURRURDUULRUUUDDLLDLDRDUURUULRUUDDLULDDRDUURUULLRDDLUUDLD

result:

ok Valid Solution (Length = 256).

Test #10:

score: 0
Accepted
time: 13ms
memory: 64004kb

input:

5 3
011
111
110
111
011
3 1 2 1

output:

ULDULRUUUUDDRLULLRRDULUDDRRLLDURLLDLRURLLDLRRLURLLLDRDUURLLLDRDRULURLLLDRDRULURLULDULRUURLUDLULRULURDRDLLLRULURDRDLLLRUUDRDLLLRULRRLDLLRURLDLLRUDLLRRDDULUDRRLLULRDDUUUURLUDLU

result:

ok Valid Solution (Length = 174).

Test #11:

score: 0
Accepted
time: 3ms
memory: 62200kb

input:

4 5
11111
11111
11111
11111
3 2 1 3

output:

UURRLLLLLLRUUDDUULLRRRRLLLUUDDURRLLLLLLRUUDDULLRRRRLLLUUDDRRLLLLLLRLLRRRRLLLUUUDDDRRLLLULLLRUUUDDDLLRRRRULLLUUUDDDLLRRRRULLLUURRLLLLLLRRUULLLURRRRLLDDDUUULLLURRRRLLDDDUUURLLLULLLRRDDDUUULLLRRRRLLRLLLLLLRRDDUULLLRRRRLLUDDUURLLLLLLRRUDDUULLLRRRRLLUUDDUURLLLLLLRRUU

result:

ok Valid Solution (Length = 262).

Test #12:

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

input:

5 5
11111
10101
11111
10101
11111
2 5 1 1

output:

ULLLLURRRRDULLLLDURRRRDULLDURRDLDRLLLLUURRRRDULLLLDDDRUUURRRRDULLDDDRUUURRDLDDRUULDDDRLLLLUUUURRRRDLDDDRLLLLUUUURRRRDULLLLLLLLUDRRRRUUUULLLLRDDDLDRRRRUUUULLLLRDDDLUURDDLDRRUUURDDDLLUDRRRRUUURDDDLLLLUDRRRRUULLLLRDLDRRUDLLUDRRRRUDLLLLUDRRRRULLLLU

result:

ok Valid Solution (Length = 244).

Test #13:

score: 0
Accepted
time: 6ms
memory: 61556kb

input:

4 5
11111
10000
11111
00001
1 3 4 5

output:

DRRRRDDLLLLUULLLLRRULLDRRRRDDUUULLLLRRULLDRRRDRDDLUULLLLRRULLDRRDRRDDUULLLLUURRLLDRDRRRDDUULLLLUURRLLDDRRRRDDUUULLLLUURRLLDDRRRRDDUUULLLLUURRDRRRRDDLLLLLLLLDDRRRRDRRUULLLLUUUDDRRRRDDLLRRUULLLLUUUDDRRRRDDLLRRUULLLLUUDDRRRDRDLLRRUULLLLUUDDRRDRRDLLURRLLLLUULDDRDRRRDLLURRLLLLUUUDDRRRRDLLURRLLLLUULLLLDDR...

result:

ok Valid Solution (Length = 304).

Test #14:

score: 0
Accepted
time: 3ms
memory: 48780kb

input:

3 5
10100
00010
00111
1 3 1 1

output:

-1

result:

ok No Solution.

Test #15:

score: 0
Accepted
time: 9ms
memory: 62096kb

input:

4 5
10001
11111
11100
11111
4 5 3 1

output:

DDLLUULLUUDRRUUDDRRUUDDLLUURRUUUUDLLDDRRDDLLULLRRUUDDRRUUDDLLLLRRRRUUDDLLLLRRRRUUDDLLUULLUULLUULLDDUURRRRLLLLDDUURRRRLLLLDDUURRDDUURRLLULLDDRRDDLLDUUUURRUULLDDUURRDDUURRDUULLUULLDD

result:

ok Valid Solution (Length = 180).

Test #16:

score: 0
Accepted
time: 3ms
memory: 62132kb

input:

3 5
11111
10100
11111
1 2 3 5

output:

RRDDRRLLLLLLUULLRRRDLLLDRRLLUULLRRRDLDRRLLURULLRDRRRDDLLLLUULLRRDRDDRRLLLURULULRDRDDRRLLLURULULRRDDRRLLLLLLLLRRDDRRLULURULLLRRDDRDRLULURULLLRRDDRDRRLLUULLLLDDRRRDRLLURULLRRDLDRRRLLUULLRRDLLLDRRRLLUULLLLLLRRDDRR

result:

ok Valid Solution (Length = 210).

Test #17:

score: -100
Wrong Answer
time: 3ms
memory: 64308kb

input:

4 5
01110
10101
11011
10111
1 3 2 3

output:

DRULLURDURLUDURLUDRULLURDULRUDULRUDRULLURD

result:

wrong answer (2,1) Not Visited