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

Judge Result