Submission #3041900
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 30;
// const int SIZE = 3;
int board[SIZE][SIZE],
longestPath[SIZE][SIZE];
int dr[4] = {1, 0, -1, 0},
dc[4] = {0, 1, 0, -1};
int randInt(int n)
{
static random_device rnd;
static mt19937 mt(rnd());
return mt() % n;
}
bool isInside(int r, int c)
{
return 0 <= r and r < SIZE and 0 <= c and c < SIZE;
}
struct Mass
{
int row, col;
Mass() {}
Mass(int row, int col) : row{row}, col{col} {}
bool operator>(const Mass& m) const
{
return board[row][col] > board[m.row][m.col];
}
};
void inputBoard()
{
for (int r = 0; r < SIZE; r++)
{
for (int c = 0; c < SIZE; c++)
{
cin >> board[r][c];
}
}
}
vector<Mass> restorePath(int startR, int startC)
{
vector<Mass> path;
int curR = startR, curC = startC;
while (isInside(curR, curC) and longestPath[curR][curC] > 0)
{
path.emplace_back(curR, curC);
int nextR = -1, nextC = -1;
for (int i = 0; i < 4; i++)
{
int nr = curR + dr[i],
nc = curC + dc[i];
if (isInside(nr, nc) and longestPath[nr][nc] + 1 == longestPath[curR][curC])
{
nextR = nr;
nextC = nc;
}
}
curR = nextR;
curC = nextC;
}
return path;
}
vector<Mass> findLongestPath()
{
priority_queue<Mass, vector<Mass>, greater<Mass>> Q;
memset(longestPath, -1, sizeof(longestPath));
for (int r = 0; r < SIZE; r++)
{
for (int c = 0; c < SIZE; c++)
{
Q.push(Mass(r, c));
}
}
int startR = -1, startC = -1;
while (!Q.empty())
{
auto m = Q.top(); Q.pop();
longestPath[m.row][m.col] = board[m.row][m.col] ? 1 : 0;
if (board[m.row][m.col] == 0) continue;
for (int i = 0; i < 4; i++)
{
int nr = m.row + dr[i],
nc = m.col + dc[i];
if (isInside(nr, nc) and board[nr][nc] == board[m.row][m.col] - 1)
{
longestPath[m.row][m.col] = max(longestPath[m.row][m.col],
longestPath[nr][nc] + 1);
}
}
if ((startR < 0 and startC < 0) or longestPath[m.row][m.col] > longestPath[startR][startC])
{
startR = m.row;
startC = m.col;
}
}
return restorePath(startR, startC);
}
vector<Mass> findGoodPath()
{
findLongestPath();
int highestR = 0, highestC = 0;
for (int r = 0; r < SIZE; r++)
{
for (int c = 0; c < SIZE; c++)
{
if (board[r][c] > board[highestR][highestR])
{
highestR = r;
highestC = c;
}
}
}
return restorePath(highestR, highestC);
}
int main()
{
inputBoard();
int turn = 1;
vector<Mass> path;
while ((path = findGoodPath()), !path.empty())
{
cerr << "[turn] " << turn++ << " [path.length] " << path.size() << endl;
/*
if (turn % 1000 == 0)
{
for (int r = 0; r < SIZE; r++)
{
for (int c = 0; c < SIZE; c++)
{
cerr << board[r][c] << " ";
}
cerr << endl;
}
}
*/
// cerr << " ==== debug end ==== " << endl;
for (auto& m : path)
{
cout << m.row + 1 << " " << m.col + 1 << endl;
board[m.row][m.col]--;
// cerr << "debug: " << board[m.row][m.col] << " => " << board[m.row][m.col] - 1 << endl;
assert(board[m.row][m.col] >= 0);
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
myusa |
Language |
C++14 (GCC 5.4.1) |
Score |
715870 |
Code Size |
3985 Byte |
Status |
AC |
Exec Time |
2461 ms |
Memory |
640 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 |
72703 / 100000 |
70928 / 100000 |
72532 / 100000 |
70244 / 100000 |
71053 / 100000 |
72168 / 100000 |
72879 / 100000 |
70431 / 100000 |
71652 / 100000 |
71280 / 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 |
2233 ms |
512 KB |
subtask_01_02.txt |
AC |
2392 ms |
512 KB |
subtask_01_03.txt |
AC |
2248 ms |
512 KB |
subtask_01_04.txt |
AC |
2461 ms |
512 KB |
subtask_01_05.txt |
AC |
2388 ms |
512 KB |
subtask_01_06.txt |
AC |
2284 ms |
512 KB |
subtask_01_07.txt |
AC |
2227 ms |
512 KB |
subtask_01_08.txt |
AC |
2417 ms |
512 KB |
subtask_01_09.txt |
AC |
2342 ms |
640 KB |
subtask_01_10.txt |
AC |
2326 ms |
512 KB |