Submission by @_gacin

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};

inline bool inBoard(int x, int y) {
    return (x >= 0 && x < 9 && y >= 0 && y < 9);
}

inline int dist(int a, int b, int c, int d) {
    return abs(a-c) + abs(b-d);
}

int t;
int X1, Y1, T1;
int X2, Y2, T2;
int c[9][9];

inline bool hae() {
    if (dist(X1, Y1, X2, Y2) > 2) return false;
    if (T2 > 3) return false;
    return true;
}

const int depth = 5;
int state[9][9];

int dfs(int px, int py, int dep) {
    if (dep == depth) return 0;
    int ret = 0;
    rep(i,4) {
        int tx = px+dx[i], ty = py+dy[i];
        if (!inBoard(tx, ty)) continue;
        int val = 0;
        if (state[tx][ty] == 0) {
            val++;
        } else if (state[tx][ty] == 2) {
            val += 2;
        }
        int pre = state[tx][ty];
        state[tx][ty] = 1;
        val += dfs(px, py, dep+1);
        state[tx][ty] = pre;
        ret = max(val, ret);
    }
    return ret;
}

int main() {
    cin >> t;
    cin >> X1 >> Y1 >> T1;
    cin >> X2 >> Y2 >> T2;
    rep(i,9) rep(j,9) cin >> c[j][i];
    if (hae()) {
        cout << 5 << endl;
        return 0;
    }
    int dir = 0;
    int val = -1;
    rep(i,4) {
        int tox = X1+dx[i], toy = Y1+dy[i];
        if (!inBoard(tox, toy)) continue;
    
        int tmp = c[tox][toy];
        int nval = 0;
        if (tmp == 0) {
            nval++;
        } else if (tmp == 2) {
            nval += 2;
        } 
        rep(j,9) rep(k,9) state[j][k] = c[j][k];
        state[tox][toy] = 1;
        nval += dfs(tox, toy, 0);
        
        if (nval > val) {
            val = nval;
            dir = i+1;
        }
    }
    cout << dir << endl;
}

Battle History