Submission #1593089

---

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;
    REP(i, h) REP(j, w) {
      if(board[i][j] > 0) {
        // 今の盤面で(i, j)からスタートして一番消せるルートを求める
        memset(d, -1, sizeof(d));
        d[i][j] = 1;
        ma = 1, gx = j, gy = i;
        dfs(i, j);
        // cout << "------------" << endl;
        // REP(k, h) {
        //   REP(l, w) {
        //     cout << d[k][l] << " ";
        //   }
        //   cout << endl;
        // }
        // cout << ma << " " << gx << " " << gy << endl;
        // ルートの長さが1だったらそれはパス
        // if(ma == 1) continue;
        // 解の復元してルートを求める
        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;
    // cout << "-----------" << endl;
    // REP(k, h) {
    //   REP(l, w) {
    //     cout << board[k][l] << " ";
    //   }
    //   cout << endl;
    // }
  }


#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