Submission #1186395

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<ctime>
using namespace std;
#pragma warning(disable:4996)
/*FILE *in = freopen("in1.txt", "r", stdin);
FILE *out = freopen("out1.txt", "w", stdout);*/

int H, W, K, T, a[453], b[453], c[453], d[453], I[33][33], dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
char Y[5] = "URDL"; bool used[33][33];
int score() {
	int ret = 0;
	for (int i = 1; i <= K; i++)ret += abs(a[i] - c[i]) + abs(b[i] - d[i]);
	return ret + 20;
}
int dist(int a1, int a2, int a3, int a4) { return abs(a1 - a3) + abs(a2 - a4); }
int main() {
	srand((unsigned)time(NULL));
	cin >> H >> W >> K >> T;
	for (int i = 1; i <= K; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; I[a[i]][b[i]] = i; }
	int maxn = 0, maxid = score(); vector<string>V;
	for (int i = 1; i <= T; i++) {
		string O = ""; for (int j = 0; j < K; j++)O += " ";
		for (int j = 1; j <= H; j++) { for (int k = 1; k <= W; k++)used[j][k] = false; }
		for (int j = 1; j <= H; j++) {
			for (int k = 1; k <= W; k++) {
				if (I[j][k] == 0 || O[I[j][k] - 1] != ' ')continue;
				bool OK = true;
				for (int l = 0; l < 4; l++) {
					int cx = j + dx[l], cy = k + dy[l], num = I[j][k];
					if (cx <= 0 || cy <= 0 || cx > H || cy > W || I[cx][cy] >= 1 || used[cx][cy] == true)continue;

					int YY = 5;
					if (i >= 7000)YY = 15;

					if (dist(cx, cy, c[I[j][k]], d[num]) > dist(j, k, c[num], d[num]) && rand()%YY < (YY - 1))continue;
					O[num - 1] = Y[l]; a[num] = cx; b[num] = cy; swap(I[cx][cy], I[j][k]); used[j][k] = true;
					OK = false; break;
				}
				if (OK == true)O[I[j][k] - 1] = '-';
			}
		}
		V.push_back(O);
		int score2 = 1000000000 / ((score())*(1000 + i));
		if (maxn < score2) { maxn = score2; maxid = i; }
	}
	cout << maxid << endl;
	for (int i = 0; i < maxid; i++) { cout << V[i] << endl; }
	return 0;
}

Submission Info

Judge Result