QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394503#7751. Palindrome PathjuruoAWA 1ms3932kbC++145.7kb2024-04-20 15:23:292024-04-20 15:23:29

Judging History

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

  • [2024-04-20 15:23:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3932kb
  • [2024-04-20 15:23:29]
  • 提交

answer

#include <bits/stdc++.h>
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse; 
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef long long li;
typedef long double lf;

inline li read(){
	li ans = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		f = (ch == '-') ? -1 : 1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans * f;
} 

li a[101][101];
pair<li, li> s, t;
li vis[101][101], n, m, sum;
li dir[101][101];
queue<pair<li, li>> q;
char move[] = {'U', 'R', 'L', 'D'};
li dx[] = {-1, 0, 0, 1};
li dy[] = {0, 1, -1, 0};
li rev[] = {3, 2, 1, 0};

li get(char s){
	if(s == 'U') return 0;
	else if(s == 'R') return 1;
	else if(s == 'L') return 2;
	else return 3;
}

void check_ifsolved(){
	li ans = 0;
	q.push(t);
	vis[t.first][t.second] = 1;
	while(!q.empty()){
		ans++;
		li x = q.front().first, y = q.front().second; q.pop();
		for(li i = 0; i < 4; i++){
			li tx = x + dx[i], ty = y + dy[i];
			if(1 <= tx && tx <= n && 1 <= ty && ty <= m && !vis[tx][ty] && a[tx][ty]){
				q.push({tx, ty});
				dir[tx][ty] = i;
				vis[tx][ty] = 1;
			}
		}
	}
	memset(vis, 0, sizeof vis);
	// cout << ans << " " << sum << endl;
	if(ans != sum){
		printf("-1\n");
		exit(0);
	}
}

bool go(li x, li y){
	if(1 <= x && x <= n && 1 <= y && y <= m){
		if(a[x][y]) return 1;
	}
	return 0;
}

string ans, temp, ans2;
bool can[35][35][35][35];
li way[35][35][35][35];
queue<pair<pair<li, li>, pair<li, li>>> qu;

// void bfs(){
// 	qu.push({s, t});
// 	can[s.first][s.second][t.first][t.second] = 1;
// 	while(!qu.empty()){
// 		auto x = qu.front().first, y = qu.front().second;
// 		if(x == y){
// 			string sum = "";
// 			while(x != s || y != t){
// 				sum += way[x.first][x.second][y.first][y.second];
				
// 			}
// 			break;
// 		}
// 		for(li i = 0; i < 4; i++){
// 			pair<li, li> tx = {x.first + dx[i], x.second + dy[i]}, ty = {y.first + dx[rev[i]], y.second + dy[rev[i]]};
// 			if(!go(tx.first, tx.second)) tx = x;
// 			if(!go(ty.first, ty.second)) continue;
// 			if(can[tx.first][tx.second][ty.first][ty.second]) continue;
// 			can[tx.first][tx.second][ty.first][ty.second] = 1;
// 			way[tx.first][tx.second][ty.first][ty.second] = i;
// 			qu.push({tx, ty});
// 		}
// 	}
// }

li dfs(pair<li, li> x, pair<li, li> y){
	// cout << x.first << " " << x.second << " " << y.first << " " << y.second << endl;
	if(x == y) return 1;
	// if(can[x.first][x.second][y.first][y.second]) return 0;
	for(li i = 0; i < 4; i++){
	// cout << "dfs " << x.first << " " << x.second << " " << y.first << " " << y.second << endl;
		pair<li, li> tx = {x.first + dx[i], x.second + dy[i]}, ty = {y.first + dx[rev[i]], y.second + dy[rev[i]]};
		if(!go(tx.first, tx.second)) tx = x;
		// printf("id = %lld:\n", i);
		// printf("to %lld %lld %lld %lld\n", tx.first, tx.second, ty.first, ty.second);
		if(go(ty.first, ty.second)){
			// printf("to %lld %lld %lld %lld\n", tx.first, tx.second, ty.first, ty.second);
			if(can[tx.first][tx.second][ty.first][ty.second]) continue;
			can[tx.first][tx.second][ty.first][ty.second] = 1;
			ans2 += move[i];
			if(dfs(tx, ty)) return 1;
			ans2.pop_back();
			// if(!go(y.first + dx[i], y.second + dy[i])) ty = y;
			// else continue;
		}
		if(!go(y.first + dx[i], y.second + dy[i])){
			ty = y;
			// printf("to %lld %lld %lld %lld\n", tx.first, tx.second, ty.first, ty.second);
			if(can[tx.first][tx.second][ty.first][ty.second]) continue;
			can[tx.first][tx.second][ty.first][ty.second] = 1;
			ans2 += move[i];
			if(dfs(tx, ty)) return 1;
			ans2.pop_back();
		}
		// can[tx.first][tx.second][ty.first][ty.second] = 0;
	}
	return 0;
}

int main(){
    // freopen("wonderful.ans", "r", stdin);
    // freopen("www.ww", "w", stdout); 
	n = read(), m = read();
	for(li i = 1; i <= n; i++){
		for(li j = 1; j <= m; j++){
			a[i][j] = getchar();
			while(a[i][j] > '1' || a[i][j] < '0') a[i][j] = getchar();
			a[i][j] -= '0';
			sum += a[i][j];
		}
	}
	s.first = read(), s.second = read(), t.first = read(), t.second = read();
	check_ifsolved();
	for(li i = 1; i <= n; i++){
		for(li j = 1; j <= m; j++){
			// puts("-----------");
			string s = "";
			if(t == make_pair(i, j)) continue;
			li x = i, y = j;
			// cout << i << " " << j << endl;
			while(t != make_pair(x, y)){
				s += move[rev[dir[x][y]]];
				x -= dx[dir[x][y]], y -= dy[dir[x][y]];
				// cout << x << " " << y << endl;
			}
			// cout << i << " " << j << endl;
			reverse(s.begin(), s.end()); 
			temp += s;
			// cout << s;
			for(li k = 0; k < s.length(); k++) s[k] = move[rev[get(s[k])]];
			reverse(s.begin(), s.end()); 
			temp += s;
			// cout << s << endl;
		}
	}
	// cout << "?" << endl;
	// reverse(temp.begin(), temp.end());
	ans += temp;
	for(char x : temp){
		li d = get(x);
		pair<li, li> tt = s;
		s.first += dx[d], s.second += dy[d];
		if(!go(s.first, s.second)){
			s = tt;
		}
		// cout << s.first << " " << s.second << endl;
	}
	// cout << "?" << endl;
 	can[s.first][s.second][t.first][t.second] = 1;
	dfs(s, t);
	// cout << ans2 << endl;
	ans += ans2;
	reverse(ans2.begin(), ans2.end());
	ans += ans2;
	reverse(temp.begin(), temp.end());
	ans += temp;
	cout << ans << endl;
    return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

DRLUDURLRDLUULDRLRUDULRD

result:

ok Valid Solution (Length = 24).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

DDDRLUUUDDDUUUDDDLRUUUDDDLLRRUUUDDRLUUDDUUDDLRUUDDLLRRUUDRLUDUDLRUDLLRRURLLRLLRRUDUDUDLUDRURDDLLUULDDDRRRDLUUUULLDRDDRDLLUUUULDRRRDDDLUULLDDRURDULDUDUDURRLLRLLRURRLLDURLDUDULRDUURRLLDDUURLDDUUDDUULRDDUUURRLLDDDUUURLDDDUUUDDDUUULRDDD

result:

ok Valid Solution (Length = 232).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

DDDDRRRRLLLLUUUUDDDDRRRLLLUUUUDDDDRRLLUUUUDDDDRLUUUUDDDDUUUUDDRRRDULLLUUDDRRDULLUUDDRDULUUDDDUUUDDDUUUDDRRRRLLLLUUDDRRRLLLUUDDRRLLUUDDRLUUDDUURRRDULLLRRDULLRDULDUDURRRRLLLLRRRLLLRRLLRLRRRRDDLLLLDDRRRRLRLLRRLLLRRRLLLLRRRRUDUDLUDRLLUDRRLLLUDRRRUUDDUULRDDUULLRRDDUULLLRRRDDUULLLLRRRRDDUUUDDDUUUDDDUULUDR...

result:

ok Valid Solution (Length = 384).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

DDUUDDLRUUDDLLRRUUDUDUDURLLRUURDULDDUUDUDDUDUURRLLDDUURLDDUUDDUURDRULLUUDDRRDDUULLURDRUUDDUUDDLRUUDDLLRRUUDUDDUDUUDDLUDRUURLLRUDUDUDUURRLLDDUURLDDUUDD

result:

wrong answer End Point Is (3,1), Not (er = 3, ec = 2)