Apparently it is about some luck as well — as you can see, there is 15% chance to not even reach the end s-shaped path when starting from its beginning and doing this kind of random walk for 1e5 moves.

Can anybody tell me how to calculate chance to pass such figure from all positions? The fact that string is good for starting from first position doesn't mean it is good for reaching finish from second cell of s-shaped labyrinth, but I have no idea how to find probability of random string being good for all possible starting positions in given labyrinth at the same time.

Just in case, I mean something like this:

####################
#C.................#
##################.#
#..................#
#.##################
#..................#
##################.#
#..................#
#.##################
#..................#
##################.#
#..................#
#.##################
#..................#
##################.#
#..................#
#.##################
#..................#
##################.#
####################

And even this particular case can be made harder with some small modifications.

Upd. And now I think I had some bugs while considering pairs/groups of cells, because after some thinking if looks like for this particular map starting from 2nd cell is strictly better than starting from 1st — in case you can reach finish from 1st cell, you can make it from 2nd as well, as first path can't simply outrun second somehow.

My solution is even worse. Atleast you are printing 10⁵ characters, I'm just printing any arbitrary dfs tree with the root of the dfs as the capital city — The length of the answer string is  < 2 * N * M.

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

const int N = 25;

char arr[N][N];
int n, m, src_x, src_y;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
char dir[] = {'D', 'U', 'R', 'L'};
int vis[N][N];
string ans = "";

inline void dfs(int x, int y){
	for(int i = 0; i < 4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		char c = dir[i];
		if(arr[nx][ny] != '*' and !vis[nx][ny]){
			vis[nx][ny] = true;
			ans += c;
			dfs(nx, ny);
			if(i & 1) ans += dir[i - 1];
			else ans += dir[i + 1];
		}
	}
}


int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> arr[i][j];
			if(arr[i][j] == 'C'){
				src_x = i;
				src_y = j;
			}
		}
	}
	vis[src_x][src_y] = true;
	dfs(src_x, src_y);
	cout << ans << '\n';
}