Fuga

Fuga.cpp

// Fuga - OBI 2018 P2 F2
// Complexidade O( 2^ ceil((n*m)/4) )

#include <bits/stdc++.h>
#define N 100050
using namespace std;

int n, m, xf, yf, xo, yo, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

int ans = 0, ini[6][6];

void solve(int x, int y, int len, int bitmask[6][6])
{
	if(x == (xf + 1)/2 - 1 and y == (yf + 1)/2 - 1)
	{
		ans = max(ans, len);

		return;
	}

	for(int i = 0; i < 4; i++)
	{
		int a = x + dx[i], b = y + dy[i];

		if(bitmask[a][b] or a < 0 or b < 0 or a >= (n + 1)/2 || b >= (m + 1)/2) continue;

		bitmask[a][b] = 1;

		solve(a, b, len + 2, bitmask);

		bitmask[a][b] = 0;

	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m>>xo>>yo>>xf>>yf;

	ini[(xo + 1)/2 - 1][(yo + 1)/2 - 1] = 1;

	solve((xo + 1)/2 - 1, (yo + 1)/2 - 1, 1, ini);

	cout<<ans<<"\n";
}