Three Pieces CodeForces - 1065D (BFS)

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <queue>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define x first

#define y second

using namespace std;

typedef pair<int,int> pii;

const int N = 15, INF = 0x3f3f3f3f;

int n;

pii a[N*N];

int f[N*N][3], g[N*N][3], d[N*N][3][3];

const int dx[]={-2,-1,1,2,2,1,-1,-2};

const int dy[]={1,2,2,1,-1,-2,-2,-1};

const int dx1[]={1,-1,1,-1};

const int dy1[]={1,1,-1,-1};

struct _ {int z,x,y;};

int dis[3][N][N], vis[3][N][N];

int chk(int x, int y) {

	return 1<=x&&x<=n&&1<=y&&y<=n;

}

int bfs(int z1, int x1, int y1, int z2, int x2, int y2) {

	queue<_> q;

	q.push({z1,x1,y1});

	memset(vis,0,sizeof vis);

	memset(dis,INF,sizeof dis);

	dis[z1][x1][y1] = 0;

	while (!q.empty()) {

		auto u = q.front();q.pop();

		if (vis[u.z][u.x][u.y]) continue;

		vis[u.z][u.x][u.y] = 1;

		int w = dis[u.z][u.x][u.y]+1;

		REP(i,0,7) {

			int xx=u.x+dx[i], yy=u.y+dy[i];

			if (!chk(xx,yy)) continue;

			dis[0][xx][yy] = min(dis[0][xx][yy], w+(u.z!=0));

			q.push({0,xx,yy});

		}

		REP(i,0,3) REP(j,1,n) {

			int xx=u.x+j*dx1[i],yy=u.y+j*dy1[i];

			if (!chk(xx,yy)) continue;

			dis[1][xx][yy] = min(dis[1][xx][yy], w+(u.z!=1));

			q.push({1,xx,yy});

		}

		REP(i,1,n) {

			dis[2][i][u.y] = min(dis[2][i][u.y], w+(u.z!=2));

			q.push({2,i,u.y});

			dis[2][u.x][i] = min(dis[2][u.x][i], w+(u.z!=2));

			q.push({2,u.x,i});

		}

	}

	return dis[z2][x2][y2];

}

int main() {

	scanf("%d", &n);

	REP(i,1,n) REP(j,1,n) {

		int t;

		scanf("%d", &t);

		a[t] = {i,j};

	}

	REP(i,2,n*n) {

		REP(j,0,2) f[i][j] = INF;

		REP(j,0,2) REP(k,0,2) {

			d[i][j][k] = bfs(k,a[i-1].x,a[i-1].y,j,a[i].x,a[i].y);

			f[i][j] = min(f[i][j], f[i-1][k]+d[i][j][k]);

		}

	}

	REP(i,2,n*n) {

		REP(j,0,2) g[i][j] = INF;

		REP(j,0,2) REP(k,0,2) {

			if (f[i-1][k]+d[i][j][k]==f[i][j]) {

				g[i][j] = min(g[i][j], g[i-1][k]+(j!=k));

			}

		}

	}

	int ans1=INF, ans2=INF;

	REP(i,0,2) ans1=min(ans1,f[n*n][i]);

	REP(i,0,2) if (ans1==f[n*n][i]) ans2=min(ans2,g[n*n][i]);

	printf("%d %d\n", ans1, ans2);

}