Submission #1593219
Source Code Expand
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
#define MAIN
const int h = 30, w = 30;
int board[30][30], d[30][30], ma, gx, gy;
int dfs(int y, int x) {
if(d[y][x] != -1) return d[y][x];
REP(i, 4) {
int ny = y + dy[i], nx = x + dx[i];
if(IN(0, w, nx) && IN(0, h, ny) && board[ny][nx] == board[y][x]+1) {
d[ny][nx] = d[y][x] + 1;
if(ma > d[ny][nx]) ma = d[ny][nx], gy = ny, gx = nx;
dfs(ny, nx);
}
}
}
signed main(void)
{
REP(i, h) REP(j, w) cin >> board[i][j];
vector<PII> ans;
int score = 0;
while(1) {
bool up = false;
int ma = 0, x = -1, y = -1;
REP(i, h) REP(j, w) {
if(ma < board[i][j]) ma = board[i][j], x = j, y = i;
}
if(ma == 0) break;
// 今の盤面で(i, j)からスタートして一番消せるルートを求める
memset(d, -1, sizeof(d));
d[y][x] = 1;
ma = 1, gx = x, gy = y;
dfs(y, x);
// 解の復元してルートを求める
up = true;
vector<PII> v;
v.PB({gy, gx});
board[gy][gx]--;
while(ma > 1) {
REP(i, 4) {
int nx = gx + dx[i], ny = gy + dy[i];
if(IN(0, w, nx) && IN(0, h, ny) && d[ny][nx]+1 == d[gy][gx]) {
gx = nx, gy = ny, ma--;
break;
}
}
board[gy][gx]--;
v.PB({gy, gx});
}
reverse(ALL(v));
copy(ALL(v), back_inserter(ans));
score++;
if(!up) break;
}
#ifdef MAIN
for(PII i: ans) cout << i.first+1 << " " << i.second+1 << endl;
#else
cout << "score:" << 100000 - score << endl;
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
541032 |
Code Size |
2374 Byte |
Status |
AC |
Exec Time |
136 ms |
Memory |
1016 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 |
Score / Max Score |
55534 / 100000 |
53221 / 100000 |
54807 / 100000 |
51866 / 100000 |
54778 / 100000 |
54564 / 100000 |
53691 / 100000 |
55284 / 100000 |
53781 / 100000 |
53506 / 100000 |
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 |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
127 ms |
1016 KB |
subtask_01_02.txt |
AC |
133 ms |
1016 KB |
subtask_01_03.txt |
AC |
129 ms |
1016 KB |
subtask_01_04.txt |
AC |
136 ms |
1016 KB |
subtask_01_05.txt |
AC |
128 ms |
1016 KB |
subtask_01_06.txt |
AC |
129 ms |
1016 KB |
subtask_01_07.txt |
AC |
132 ms |
1016 KB |
subtask_01_08.txt |
AC |
127 ms |
1016 KB |
subtask_01_09.txt |
AC |
132 ms |
1016 KB |
subtask_01_10.txt |
AC |
134 ms |
1016 KB |