\(S\)、\(T\) それぞれの盤面から開始して、\(15\) 手以内に到達可能な盤面を幅優先探索などで全て列挙すれば、両方から到達可能な盤面について \(S\) からの最短手数と \(T\) からの最短手数の和を求めてその最小値を出力することでこの問題に答えることができます。

計算量を見積もります。\(S\) から開始して最初の \(1\) 手目の候補は上下左右いずれを選ぶかの \(4\) 通りです。\(2\) 手目以降については、直前の操作で動かした手順を戻す操作はすでに探索済みのため、候補となる手は \(3\) 通りしかありません。結局、この幅優先探索でかかる計算回数は \(4 \times 3^{14} \simeq 2 \times 10^7\) 程度であり、実行時間制限に間に合います。

#include <bits/stdc++.h>
using namespace std;
const vector<pair<int,int>> dxy = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int main() {
    vector s(4, vector<int>(4));
    vector t(4, vector<int>(4));
    for (int i=0; i<4; i++) for (int j=0; j<4; j++) cin >> s[i][j];
    for (int i=0; i<4; i++) for (int j=0; j<4; j++) cin >> t[i][j];
    auto calc_dp = [&] (const vector<vector<int>>& s) -> map<vector<vector<int>>, int> {
        deque<vector<vector<int>>> q = {s};
        map<vector<vector<int>>, int> dp;
        dp[s] = 0;
        while (!q.empty()) {
            auto s = q.front(); q.pop_front();
            int x = -1, y = -1;
            for (int i=0; i<4; i++) for (int j=0; j<4; j++) if (s[i][j] == -1) {x = i; y = j;}
            for (auto [dx, dy] : dxy) {
                if (x+dx < 0 || x+dx >= 4 || y+dy < 0 || y+dy >= 4) continue;
                auto sn = s;
                swap(sn[x+dx][y+dy], sn[x][y]);
                if (dp.count(sn) == 0) {
                    dp[sn] = dp[s] + 1;
                    if (dp[sn] < 15) q.push_back(sn);
                }
            }
        }
        return dp;
    };
    auto dps = calc_dp(s);
    auto dpt = calc_dp(t);
    int ans = 40;
    for (auto [k, v] : dps) {
        if (!dpt.count(k)) continue;
        if (ans > v + dpt[k]) ans = v + dpt[k];
    }
    if (ans == 40) ans = -1;
    cout << ans << '\n';
}