QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394546#7751. Palindrome PathlfxxxWA 0ms4100kbC++173.9kb2024-04-20 15:59:352024-04-20 15:59:36

Judging History

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

  • [2024-04-20 15:59:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4100kb
  • [2024-04-20 15:59:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 35;
int n, m, x, y, xx, yy;
char pre[N][N];
char a[N][N];
bool vis[N][N];
string s, ans;
#define ck(x, y) (1 <= x && x <= n && 1 <= y && y <= m && !vis[x][y])
void dfs(int x, int y)
{
	vis[x][y] = 1;
	if (ck(x + 1, y)) {
		ans += "U";
		dfs(x + 1, y);
		ans += "D";
	}
	if (ck(x - 1, y)) {
		ans += "D";
		dfs(x - 1, y);
		ans += "U";
	}
	if (ck(x, y + 1)) {
		vis[x][y + 1] = 1;
		ans += "L";
		dfs(x, y + 1);
		ans += "R";
	}
	if (ck(x, y - 1)) {
		vis[x][y - 1] = 1;
		ans += "R";
		dfs(x, y - 1);
		ans += "L";
	}
}
void D()
{
	int d = 0;
	while (a[x + d + 1][y] == '1' && a[xx - d - 1][yy] == '1') ++d;
	if (a[xx - d - 1][yy] == '1') {
		for (int i = 0; i <= d; ++i) ans += 'U';
		for (int i = 0; i <= d; ++i) ans += 'D';
	} else {
		for (int i = 1; i <= d; ++i) ans += 'U';
		for (int i = 0; i <= d; ++i) ans += 'D';
	}
}
void U()
{
	int d = 0;
	while (a[x - d - 1][y] == '1' && a[xx + d + 1][yy] == '1') ++d;
	if (a[xx + d + 1][yy] == '1') {
		for (int i = 0; i <= d; ++i) ans += 'D';
		for (int i = 0; i <= d; ++i) ans += 'U';
	} else {
		for (int i = 1; i <= d; ++i) ans += 'D';
		for (int i = 0; i <= d; ++i) ans += 'U';
	}
}
void R()
{	int d = 0;
	while (a[x][y - d - 1] == '1' && a[xx][yy + d + 1] == '1') ++d;
	if (a[xx][yy + d + 1] == '1') {
		for (int i = 0; i <= d; ++i) ans += 'L';
		for (int i = 0; i <= d; ++i) ans += 'R';
	} else {
		for (int i = 1; i <= d; ++i) ans += 'L';
		for (int i = 0; i <= d; ++i) ans += 'R';
	}
}
void L()
{
	int d = 0;
	while (a[x][y + d + 1] == '1' && a[xx][yy - d - 1] == '1') ++d;
	if (a[xx][yy - d - 1] == '1') {
		for (int i = 0; i <= d; ++i) ans += 'R';
		for (int i = 0; i <= d; ++i) ans += 'L';
	} else {
		for (int i = 1; i <= d; ++i) ans += 'R';
		for (int i = 0; i <= d; ++i) ans += 'L';
	}
}
void bfs()
{
	queue<pii>q;
	q.emplace(x, y);
	vis[x][y] = 1;
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		if (ck(x + 1, y)) {
			vis[x + 1][y] = 1;
			pre[x + 1][y] = 'D';
			q.emplace(x + 1, y);
		}
		if (ck(x - 1, y)) {
			vis[x - 1][y] = 1;
			pre[x - 1][y] = 'U';
			q.emplace(x - 1, y);
		}
		if (ck(x, y + 1)) {
			vis[x][y + 1] = 1;
			pre[x][y + 1] = 'R';
			q.emplace(x, y + 1);
		}
		if (ck(x, y - 1)) {
			vis[x][y - 1] = 1;
			pre[x][y - 1] = 'L';
			q.emplace(x, y - 1);
		}
	}
}
bool en;
int main() {
	cerr << (&be - &en) / 1024.0 / 1024 << " MB\n--------------------------------" << endl;
#ifdef IAKIOI
	freopen("in.in", "r", stdin);
//	freopen("out.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
			if (a[i][j] == '0') vis[i][j] = 1;
		}
	}
	cin >> x >> y >> xx >> yy;
	dfs(xx, yy);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (a[i][j] == '1' && !vis[i][j]) {
				cout << "-1\n";
				return 0;
			}
		}
	}
	for (char c : ans) {
		if (c == 'U') {
			if (a[x - 1][y] == '1') --x;
		} else if (c == 'D') {
			if (a[x + 1][y] == '1') ++x;
		} else if (c == 'R') {
			if (a[x][y + 1] == '1') ++y;
		} else {
			if (a[x][y - 1] == '1') --y;
		}
	}
	memset(vis, 0, sizeof vis);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (a[i][j] == '0') vis[i][j] = 1;
		}
	}
	bfs();
	while (xx != x || yy != y) {
		s += pre[xx][yy];
		if (pre[xx][yy] == 'D') --xx;
		else if (pre[xx][yy] == 'U') ++xx;
		else if (pre[xx][yy] == 'R') --yy;
		else ++yy;
	}
	reverse(all(s));
	for (char c : s) {
		if (c == 'D') D(), ++x;
		else if (c == 'U') U(), --x;
		else if (c == 'R') R(), ++y;
		else L(), --y;
	}
	cout << ans;
	reverse(all(ans));
	cout << ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

DRUDLUDLRRLDULDURD

result:

ok Valid Solution (Length = 18).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

ULDDDDLUUUUDDDDRRUURUUDDDDUULDDLUUUURDUDDUDDRRLLLLRRDDUDDUDRUUUULDDLUUDDDDUURUURRDDDDUUUULDDDDLU

result:

ok Valid Solution (Length = 96).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

DDDDRRUUUULRRRDDDDLRUULRUULLDDLRDDLLUUUUDDDDLRLLRRLLLRRRLLLLRRRRRRRRLLLLRRRLLLRRLLRLDDDDUUUULLDDRLDDLLUURLUURLDDDDRRRLUUUURRDDDD

result:

ok Valid Solution (Length = 128).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

LUURRLLDDRRDDLLRRUULLUURRLLDDRRDDLLRRUUL

result:

ok Valid Solution (Length = 40).

Test #7:

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

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

UULDULUUDLDDDUUURDRRDDURLUULRUDDRRDRUUUDDDLDUULUDLUU

result:

ok Valid Solution (Length = 52).

Test #8:

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

input:

5 3
101
111
100
111
100
4 1 2 2

output:

LDURRUUUDLLRRDDDULRLLUULRRLUULLRLUDDDRRLLDUUURRUDL

result:

ok Valid Solution (Length = 50).

Test #9:

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

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

DDDULUULRDDLDDLUUULRDDDRRLUURRUUDDRLRRLLDDRRLLLLRRDDLLRRLRDDUURRUULRRDDDRLUUULDDLDDRLUULUDDD

result:

wrong answer (4,5) Not Visited