Submission #1173246
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int vy[] = {-1, 0, 1, 0}, vx[] = {0, 1, 0, -1};
const string vv = "URDL";
int H, W, K, T, A[450], B[450], C[450], D[450];
bool isover(int y, int x)
{
return (y < 0 || y >= H || x < 0 || x >= W);
}
int getCost(int y, int x, int id)
{
return (abs(y - C[id]) + abs(x - D[id]));
}
struct State
{
int mas[30][30];
vector< string > dd;
int score;
State()
{
memset(mas, -1, sizeof(mas));
}
int getScore()
{
int Pd = 20;
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
if(~mas[i][j]) Pd += abs(C[mas[i][j]] - i) + abs(D[mas[i][j]] - j);
}
}
double Pt = 10 + (int) dd.back().size() * 0.01;
return ((int) ceil(10000000 / (Pd * Pt)));
}
};
int main()
{
cin >> H >> W >> K >> T;
int S[500][500];
memset(S, -1, sizeof(S));
for(int i = 0; i < K; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
--A[i], --B[i], --C[i], --D[i];
S[A[i]][B[i]] = i;
}
int lim = 25;
char dd[lim][450];
for(int i = 0; i < lim; i++) {
int T[500][500];
memset(T, -1, sizeof(T));
for(int j = 0; j < H; j++) {
for(int k = 0; k < W; k++) {
if(~S[j][k]) {
char flop = '-';
int id = S[j][k];
for(int l = 0; l < 4; l++) {
int ny = j + vy[l], nx = k + vx[l];
if(isover(ny, nx)) continue;
int predist = getCost(j, k, id);
int curdist = getCost(ny, nx, id);
if(predist > curdist && T[ny][nx] == -1 && S[ny][nx] == -1) {
T[ny][nx] = id;
flop = vv[l];
break;
}
}
if(flop == '-') T[j][k] = id;
dd[i][id] = flop;
}
}
}
swap(S, T);
}
cout << lim << endl;
for(int i = 0; i < lim; i++) {
for(int j = 0; j < K; j++) cout << dd[i][j];
cout << endl;
}
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
ei13333 |
Language |
C++14 (GCC 5.4.1) |
Score |
4617 |
Code Size |
2008 Byte |
Status |
AC |
Exec Time |
31 ms |
Memory |
2176 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
test_11 |
test_12 |
test_13 |
test_14 |
test_15 |
test_16 |
test_17 |
test_18 |
test_19 |
test_20 |
test_21 |
test_22 |
test_23 |
test_24 |
test_25 |
test_26 |
test_27 |
test_28 |
test_29 |
test_30 |
Score / Max Score |
159 / 50000 |
159 / 50000 |
154 / 50000 |
159 / 50000 |
171 / 50000 |
152 / 50000 |
153 / 50000 |
163 / 50000 |
145 / 50000 |
152 / 50000 |
162 / 50000 |
150 / 50000 |
149 / 50000 |
161 / 50000 |
148 / 50000 |
162 / 50000 |
151 / 50000 |
150 / 50000 |
154 / 50000 |
153 / 50000 |
162 / 50000 |
149 / 50000 |
151 / 50000 |
146 / 50000 |
147 / 50000 |
155 / 50000 |
156 / 50000 |
140 / 50000 |
152 / 50000 |
152 / 50000 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
test_11 |
subtask_01_11.txt |
test_12 |
subtask_01_12.txt |
test_13 |
subtask_01_13.txt |
test_14 |
subtask_01_14.txt |
test_15 |
subtask_01_15.txt |
test_16 |
subtask_01_16.txt |
test_17 |
subtask_01_17.txt |
test_18 |
subtask_01_18.txt |
test_19 |
subtask_01_19.txt |
test_20 |
subtask_01_20.txt |
test_21 |
subtask_01_21.txt |
test_22 |
subtask_01_22.txt |
test_23 |
subtask_01_23.txt |
test_24 |
subtask_01_24.txt |
test_25 |
subtask_01_25.txt |
test_26 |
subtask_01_26.txt |
test_27 |
subtask_01_27.txt |
test_28 |
subtask_01_28.txt |
test_29 |
subtask_01_29.txt |
test_30 |
subtask_01_30.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
9 ms |
2176 KB |
subtask_01_02.txt |
AC |
9 ms |
2176 KB |
subtask_01_03.txt |
AC |
9 ms |
2176 KB |
subtask_01_04.txt |
AC |
9 ms |
2176 KB |
subtask_01_05.txt |
AC |
9 ms |
2176 KB |
subtask_01_06.txt |
AC |
9 ms |
2176 KB |
subtask_01_07.txt |
AC |
9 ms |
2176 KB |
subtask_01_08.txt |
AC |
9 ms |
2176 KB |
subtask_01_09.txt |
AC |
9 ms |
2176 KB |
subtask_01_10.txt |
AC |
9 ms |
2176 KB |
subtask_01_11.txt |
AC |
9 ms |
2176 KB |
subtask_01_12.txt |
AC |
9 ms |
2176 KB |
subtask_01_13.txt |
AC |
9 ms |
2176 KB |
subtask_01_14.txt |
AC |
9 ms |
2176 KB |
subtask_01_15.txt |
AC |
9 ms |
2176 KB |
subtask_01_16.txt |
AC |
9 ms |
2176 KB |
subtask_01_17.txt |
AC |
9 ms |
2176 KB |
subtask_01_18.txt |
AC |
9 ms |
2176 KB |
subtask_01_19.txt |
AC |
9 ms |
2176 KB |
subtask_01_20.txt |
AC |
9 ms |
2176 KB |
subtask_01_21.txt |
AC |
9 ms |
2176 KB |
subtask_01_22.txt |
AC |
9 ms |
2176 KB |
subtask_01_23.txt |
AC |
9 ms |
2176 KB |
subtask_01_24.txt |
AC |
9 ms |
2176 KB |
subtask_01_25.txt |
AC |
31 ms |
2176 KB |
subtask_01_26.txt |
AC |
9 ms |
2176 KB |
subtask_01_27.txt |
AC |
9 ms |
2176 KB |
subtask_01_28.txt |
AC |
9 ms |
2176 KB |
subtask_01_29.txt |
AC |
9 ms |
2176 KB |
subtask_01_30.txt |
AC |
9 ms |
2176 KB |