Submission #1139856
Source Code Expand
#include <iostream>
#include <vector>
#include <random>
#include <list>
#include <set>
using namespace std;
// template for creating 2d vector
template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }
typedef vector< vector<int> > two_d_vector;
random_device rnd;
#define debug(x) cout << #x << "==" << x << endl;
const int inf = 100000000;
typedef long long ll;
#define N 30
auto A = make_2d_vector(N, N, 0);
//移動4方向のベクトル
int di[4] = {-1, 0, 0, 1};
int dj[4] = {0, -1, 1, 0};
typedef pair<int,int> P;
bool in_bound(P p) {
return (p.first < N) && (0 <= p.first) && (p.second < N) && (0 <= p.second);;
}
void print_A() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cout << A[i][j] << " ";
} cout << "\n";
} cout << "\n";
}
void print_pos(P p) {
cout << p.first+1 << " " << p.second+1 << "\n";
}
void minus_path(list<P> &lp) {
for(auto itr = lp.begin(); itr != lp.end(); ++itr) {
P p = *itr;
print_pos(p);
A[p.first][p.second]--;
}
}
void get_path(P p, set<P> &visited, list<P> &path) {
int i = p.first; int j = p.second;
if( A[i][j] == 0 ) {
return;
}
path.push_back( p );
visited.insert( p );
vector< P > next_cand;
vector< P > next_same;
for(int k = 0; k < 4; k++) {
int ni = i + di[k]; int nj = j + dj[k];
P np = P(ni, nj);
if( in_bound(np) ) {
if( A[ni][nj] == A[i][j]-1 ) {
next_cand.push_back( np );
} else if ( (A[ni][nj] == A[i][j]) && (visited.count(np) == 0) ) {
next_same.push_back( np );
}
}
}
if( next_cand.size() != 0 ) {
P np = next_cand[ 0 ];
get_path( np , visited, path);
} else if( next_same.size() != 0 ) {
path.clear();
P np = next_same[ 0 ];
get_path( np, visited , path);
}
}
P get_max_index() {
P max_index;
int max_n = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int n = A[i][j];
if(max_n < n) {
max_index = P(i,j);
max_n = n;
} // else if (max_n == n) {
// if( rnd() % 2 == 0 ) max_index = P(i,j);
// }
}
}
return max_index;
}
int get_A(P p) {
return A[p.first][p.second];
}
int main() {
ios::sync_with_stdio(false);
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
P mxp = get_max_index();
while(true) {
set<P> visited;
if( A[mxp.first][mxp.second] == 0) { break; }
list<P> path;
get_path( mxp, visited, path);
int num = get_A(mxp);
minus_path(path);
if( get_A(mxp) != num ) { mxp = get_max_index(); }
}
return 0;
}
// 9 8 7 6 5 8 7 6 5 4 3
// 9 8 7 6 5 4 7 6 5 4 3
// 0 8 0
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
sadtomato |
Language |
C++14 (Clang 3.8.0) |
Score |
842060 |
Code Size |
2916 Byte |
Status |
AC |
Exec Time |
51 ms |
Memory |
512 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 |
84069 / 100000 |
84117 / 100000 |
84099 / 100000 |
83888 / 100000 |
84180 / 100000 |
84022 / 100000 |
84628 / 100000 |
84312 / 100000 |
84595 / 100000 |
84150 / 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 |
49 ms |
512 KB |
subtask_01_02.txt |
AC |
50 ms |
512 KB |
subtask_01_03.txt |
AC |
49 ms |
512 KB |
subtask_01_04.txt |
AC |
51 ms |
512 KB |
subtask_01_05.txt |
AC |
49 ms |
512 KB |
subtask_01_06.txt |
AC |
50 ms |
512 KB |
subtask_01_07.txt |
AC |
51 ms |
512 KB |
subtask_01_08.txt |
AC |
49 ms |
512 KB |
subtask_01_09.txt |
AC |
49 ms |
512 KB |
subtask_01_10.txt |
AC |
51 ms |
512 KB |