QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#339245#7751. Palindrome Pathsinsop90TL 0ms0kbC++141.8kb2024-02-26 21:42:562024-02-26 21:42:57

Judging History

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

  • [2024-02-26 21:42:57]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-02-26 21:42:56]
  • 提交

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) {
//	cout << x << " " << y << " " << op << '\n';
	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[j][0], yy = y + fx[j][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

output:


result: