Submission #1174981

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cstdlib>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 0x3fffffff;


int H, W, K, T;
int A[500], B[500], C[500], D[500];
int cr[10005][50][50];

vector<string> move(){
	vector<string> ret;

	for(int i=ret.size(); i<T; i++){
		string s(K, '-');
		bool f = true;
		rep(k,K){
			auto cur = pii(B[k], A[k]);
			int x = D[k];
			int y = C[k];
			if( i < 200 && rand() % 100 < 50 ){
				x = (int)(2*x > W) * (W-1);
				y = (int)(2*y > H) * (H-1);
			}
			cr[i+1][ cur.Y ][ cur.X ] = k;
			{
				//int rate = (i-200)*(i-200)/1000 + 10;
				int rate = i/100 + 10;
				if( i > 400 ) rate += i*i;
				if( rand() % rate == 0 ) x = min(W-1, cur.X+1);
				else if( rand() % rate == 0 ) x = max(0,   cur.X-1);
				else if( rand() % rate == 0 ) y = min(H-1, cur.Y+1);
				else if( rand() % rate == 0 ) y = max(0,   cur.Y-1);
			}
			if( x > cur.X && cr[i][ cur.Y ][ cur.X+1 ] == -1 && cr[i+1][ cur.Y ][ cur.X+1 ] == -1 ){
				s[k] = 'R';
				B[k]++;
				cr[i+1][ cur.Y ][ cur.X ] = -1;
				cr[i+1][ cur.Y ][ cur.X+1 ] = k;
				f = false;
			}else if( x < cur.X && cr[i][ cur.Y ][ cur.X-1 ] == -1 && cr[i+1][ cur.Y ][ cur.X-1 ] == -1 ){
				s[k] = 'L';
				B[k]--;
				cr[i+1][ cur.Y ][ cur.X ] = -1;
				cr[i+1][ cur.Y ][ cur.X-1 ] = k;
				f = false;
			}else if( cur.Y < y && cr[i][ cur.Y+1 ][ cur.X ] == -1 && cr[i+1][ cur.Y+1 ][ cur.X ] == -1){
				s[k] = 'D';
				A[k]++;
				cr[i+1][ cur.Y ][ cur.X ] = -1;
				cr[i+1][ cur.Y+1 ][ cur.X ] = k;
				f = false;
			}else if( cur.Y > y && cr[i][ cur.Y-1 ][ cur.X ] == -1 && cr[i+1][ cur.Y-1 ][ cur.X ] == -1){
				s[k] = 'U';
				A[k]--;
				cr[i+1][ cur.Y ][ cur.X ] = -1;
				cr[i+1][ cur.Y-1 ][ cur.X ] = k;
				f = false;
			}
		}
		if(f) break;
		ret.push_back( s );
	}

	return ret;
}

int main(){
	//ios_base::sync_with_stdio(0);
	Fill(cr, -1);

	srand(10);

	cin >> H >> W >> K >> T;
	rep(i,K){
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		A[i]--;
		B[i]--;
		C[i]--;
		D[i]--;
		cr[0][ A[i] ][ B[i] ] = i;
	}

	auto ans = move();
	cout << ans.size() << endl;
	for(auto t: ans){
		cout << t << endl;
	}

	return 0;
}

Submission Info

Judge Result