QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394452#7751. Palindrome PathoscaryangWA 2ms14116kbC++173.3kb2024-04-20 14:52:202024-04-20 14:52:20

Judging History

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

  • [2024-04-20 14:52:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:14116kb
  • [2024-04-20 14:52:20]
  • 提交

answer

#include<bits/stdc++.h>

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
bool st;

mt19937 gen(time(0));

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 35;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
// R L D U

int n, m, sx, sy, tx, ty, tot, cnt, vis[N][N];
int f[N][N][N][N], g[N][N][N][N];
pii s[N][N][N][N], t[N][N][N][N];
struct node { int x, y, u, v; };
char a[N][N], CH[4];
vc <int> S;
vc <char> ans;

inline int ok (int x, int y) { return x > 0 && x <= n && y > 0 && y <= m && a[x][y] == '1'; }

inline int same (int x, int y, int u, int v) { return x == u && y == v; }

inline int adj (int x, int y, int u, int v) { return (x == u && abs (y - v) == 1) || (y == v && abs (x - u) == 1); }

inline void to (int &x, int &y, int i) { 
	int u = x + dx[i], v = y + dy[i];
	if (ok (u, v)) x = u, y = v;
}

inline void dfs (int x, int y) {
	// cerr << x << " " << y << endl;
	vis[x][y] = 1; ++ cnt;
	rep (i, 0, 3) {
		int u = x + dx[i], v = y + dy[i];
		if (!ok (u, v) || vis[u][v]) continue;
		S.pb (i);
		dfs (u, v);
		S.pb (i ^ 1); 
	}
}

inline void construct (int x, int y, int u, int v) {
	vc <int> res; int mid = -1;
	if (!same (x, y, u, v)) {
		if (x == u) mid = y < v ? 0 : 1;
		else mid = x < u ? 2 : 3;
	}
	while (!same (x, y, sx, sy) || !same (u, v, tx, ty)) {
		res.pb (g[x][y][u][v]);
		auto [a, b] = s[x][y][u][v];
		auto [c, d] = t[x][y][u][v];
		x = a; y = b; u = c; v = d;
	}
	reverse (res.begin (), res.end ());
	for (auto u : res) S.pb (u);
	for (auto u : S) ans.pb (CH[u]);
	if (mid != -1) ans.pb (CH[mid]);
	reverse (S.begin (), S.end ());
	for (auto u : S) ans.pb (CH[u]);
}

inline void bfs () {
	queue <node> Q;
	Q.push (node {sx, sy, tx, ty});
	f[sx][sy][tx][ty] = 1;
	while (!Q.empty ()) {
		auto [x, y, u, v] = Q.front (); Q.pop ();
		if (same (x, y, u, v) || adj (x, y, u, v)) return construct (x, y, u, v);
		rep (i, 0, 3) {
			int a, b, c, d;
			if (ok (a = u + dx[i ^ 1], b = v + dy[i ^ 1])) {
				to (c = x, d = y, i);
				if (!f[c][d][a][b]) {
					f[c][d][a][b] = 1;
					g[c][d][a][b] = i;
					s[c][d][a][b] = mkp (x, y);
					t[c][d][a][b] = mkp (u, v);
					Q.push (node {c, d, a, b});
				}
			}
			if (!ok (a = u + dx[i], b = v + dy[i])) {
				to (c = x, d = y, i);
				if (!f[c][d][a][b]) {
					f[c][d][a][b] = 1;
					g[c][d][a][b] = i;
					s[c][d][a][b] = mkp (x, y);
					t[c][d][a][b] = mkp (u, v);
					Q.push (node {c, d, a, b});
				}
			}
		}
	}
}

bool ed;
signed main() {
	cerr << (&ed - &st) / 1024 / 1024 << "MB ---------------------------" << endl;
	CH[0] = 'R', CH[1] = 'L'; CH[2] = 'D'; CH[3] = 'U';
	
	n = read (); m = read ();
	rep (i, 1, n) scanf ("%s", a[i] + 1);
	rep (i, 1, n) rep (j, 1, m) tot += a[i][j] == '1';
	
	sx = read (); sy = read (); tx = read (); ty = read ();
	
	dfs (tx, ty);
	if (cnt < tot) return puts ("-1"), 0;
	reverse (S.begin (), S.end ());
	for (auto u : S) to (sx, sy, u);
	
	bfs ();
	
	for (auto u : ans) putchar (u); putchar (10);
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

RDLRULRRDRRLURLDR

result:

ok Valid Solution (Length = 17).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 1ms
memory: 5776kb

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

score: 0
Accepted
time: 2ms
memory: 12336kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

LLURRRDDLLLDRRRDLLLRRRULLLURRRUULLLDRRDLDRRDLLLUURRRULLLURRRLLLDRRRDLLLDDRRRULL

result:

ok Valid Solution (Length = 79).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

RRRRDDLLUDLLDDRRUDRRUDLLLLUUUDRRRRUULLLLRRDDDDRRLLLLUURRRRDUUULLLLDURRDURRDDLLDULLDDRRRR

result:

ok Valid Solution (Length = 88).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

RDDLLRRUULLUURRLLDDRRDDLLRRUULLUURRLLDDR

result:

ok Valid Solution (Length = 40).

Test #7:

score: 0
Accepted
time: 2ms
memory: 14032kb

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

ULURLLLDDUUURUDLDRRDRDULULULUDRDRRDLDURUUUDDLLLRULU

result:

ok Valid Solution (Length = 51).

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 9872kb

input:

5 3
101
111
100
111
100
4 1 2 2

output:

RDUUUUDLLRRDDLLDURDUDRUDLLDDRRLLDUUUUDR

result:

wrong answer (1,3) Not Visited