Submission #1173448
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define for_(i,a,b) for(int i=(a);i<(b);++i)
const int DX[4] = {0,1,0,-1}, DY[4] = {-1,0,1,0};
template< typename T >
inline bool in_range(T v, T mi, T mx) { return mi <= v && v < mx; }
template< typename T >
inline bool in_range(T x, T y, T W, T H) { return in_range(x,0,W) && in_range(y,0,H); }
//
string movestr = "URDL-";
int H, W, K, T, A[450], B[450], C[450], D[450];
bool board[33][33];
void construct() {
memset(board, 0, sizeof(board));
for_(i,0,K) board[A[i]][B[i]] = true;
}
void greedyMovement() {
vector< string > ans;
for_(rep,0,T) {
string movement;
construct();
for_(i,0,K) {
int cur_dst = abs(C[i] - A[i]) + abs(D[i] - B[i]);
bool move_flag = false;
for_(d,0,4) {
int nx = B[i] + DX[d], ny = A[i] + DY[d];
if (!in_range(nx, ny, W, H)) continue;
if (board[ny][nx]) continue;
int nxt_dst = abs(C[i] - ny) + abs(D[i] - nx);
if (nxt_dst < cur_dst) {
// move
movement += movestr[d];
A[i] = ny;
B[i] = nx;
move_flag = true;
board[ny][nx] = true;
break;
}
}
if (!move_flag) movement += "-";
}
bool end = true;
for_(i,0,K) end &= (movement[i] == '-');
if (end) break;
ans.push_back(movement);
}
int m = ans.size();
cout << m << endl;
for_(i,0,m) cout << ans[i] << endl;
}
int main() {
cin >> H >> W >> K >> T;
for_(i,0,K) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
--A[i]; --B[i]; --C[i]; --D[i];
}
greedyMovement();
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
tsukasa_diary |
Language |
C++14 (GCC 5.4.1) |
Score |
4655 |
Code Size |
1584 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
256 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 |
164 / 50000 |
159 / 50000 |
156 / 50000 |
162 / 50000 |
172 / 50000 |
156 / 50000 |
156 / 50000 |
165 / 50000 |
148 / 50000 |
148 / 50000 |
164 / 50000 |
160 / 50000 |
149 / 50000 |
165 / 50000 |
147 / 50000 |
166 / 50000 |
150 / 50000 |
148 / 50000 |
154 / 50000 |
151 / 50000 |
159 / 50000 |
152 / 50000 |
150 / 50000 |
143 / 50000 |
151 / 50000 |
156 / 50000 |
154 / 50000 |
142 / 50000 |
155 / 50000 |
153 / 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 |
2 ms |
256 KB |
subtask_01_02.txt |
AC |
2 ms |
256 KB |
subtask_01_03.txt |
AC |
2 ms |
256 KB |
subtask_01_04.txt |
AC |
2 ms |
256 KB |
subtask_01_05.txt |
AC |
2 ms |
256 KB |
subtask_01_06.txt |
AC |
2 ms |
256 KB |
subtask_01_07.txt |
AC |
2 ms |
256 KB |
subtask_01_08.txt |
AC |
2 ms |
256 KB |
subtask_01_09.txt |
AC |
2 ms |
256 KB |
subtask_01_10.txt |
AC |
2 ms |
256 KB |
subtask_01_11.txt |
AC |
2 ms |
256 KB |
subtask_01_12.txt |
AC |
2 ms |
256 KB |
subtask_01_13.txt |
AC |
2 ms |
256 KB |
subtask_01_14.txt |
AC |
2 ms |
256 KB |
subtask_01_15.txt |
AC |
2 ms |
256 KB |
subtask_01_16.txt |
AC |
2 ms |
256 KB |
subtask_01_17.txt |
AC |
2 ms |
256 KB |
subtask_01_18.txt |
AC |
2 ms |
256 KB |
subtask_01_19.txt |
AC |
2 ms |
256 KB |
subtask_01_20.txt |
AC |
2 ms |
256 KB |
subtask_01_21.txt |
AC |
2 ms |
256 KB |
subtask_01_22.txt |
AC |
2 ms |
256 KB |
subtask_01_23.txt |
AC |
2 ms |
256 KB |
subtask_01_24.txt |
AC |
2 ms |
256 KB |
subtask_01_25.txt |
AC |
2 ms |
256 KB |
subtask_01_26.txt |
AC |
2 ms |
256 KB |
subtask_01_27.txt |
AC |
2 ms |
256 KB |
subtask_01_28.txt |
AC |
2 ms |
256 KB |
subtask_01_29.txt |
AC |
2 ms |
256 KB |
subtask_01_30.txt |
AC |
2 ms |
256 KB |