Submission #1139868

---

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]--;
  }
}

bool is_slope(P p) {
  int i = p.first; int j = p.second;
  bool up = false;
  bool down = false;
  for(int k = 0; k < 4; k++) {
    int ni = i + di[k]; int nj = j + dj[k];
    if( in_bound( P(ni,nj) ) && (A[i][j] - 1 == A[ni][nj]) ) down = true;
    if( in_bound( P(ni,nj) ) && (A[i][j] + 1 == A[ni][nj]) ) up   = true;
  }
  return up && down;
}

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_down;
  vector< P > next_same;
  vector< P > next_up;
  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) && (visited.count(np) == 0) )  {
        next_down.push_back( np );
      } else if ( (A[ni][nj] == A[i][j]) && (visited.count(np) == 0) ) {
        next_same.push_back( np );
      } else if ( (A[ni][nj] > A[i][j]) &&  (visited.count(np) == 0) && !is_slope(np) ) {
        next_up.push_back( np );
      }
    }
  }

  if( next_down.size() != 0 ) {
    P np = next_down[ 0 ];
    get_path( np , visited, path);
  } else if( next_same.size() != 0 ) {
    path.clear();
    P np = next_same[ 0 ];
    get_path( np, visited , path);
  } else if( next_up.size() != 0 ) {
    path.clear();
    P np = next_up[ 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

Judge Result