Submission #3041758
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()
{
vector<Mass> path = 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;
}
}
}
if (randInt(3) == 0) path = restorePath(highestR, highestC);
return path;
}
int main()
{
inputBoard();
int turn = 1;
vector<Mass> path;
while ((path = findLongestPath()), !path.empty())
{
cerr << "[turn] " << turn++ << " [path.length] " << path.size() << endl;
/*
for (int r = 0; r < SIZE; r++)
{
for (int c = 0; c < SIZE; c++)
{
cerr << longestPath[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 |
575699 |
Code Size |
3966 Byte |
Status |
AC |
Exec Time |
3268 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 |
59520 / 100000 |
55791 / 100000 |
58246 / 100000 |
56544 / 100000 |
57756 / 100000 |
57731 / 100000 |
56994 / 100000 |
59539 / 100000 |
57160 / 100000 |
56418 / 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 |
2975 ms |
512 KB |
subtask_01_02.txt |
AC |
3268 ms |
512 KB |
subtask_01_03.txt |
AC |
3077 ms |
640 KB |
subtask_01_04.txt |
AC |
3236 ms |
512 KB |
subtask_01_05.txt |
AC |
3152 ms |
512 KB |
subtask_01_06.txt |
AC |
3144 ms |
512 KB |
subtask_01_07.txt |
AC |
3188 ms |
640 KB |
subtask_01_08.txt |
AC |
2982 ms |
512 KB |
subtask_01_09.txt |
AC |
3179 ms |
512 KB |
subtask_01_10.txt |
AC |
3247 ms |
640 KB |