ROBOCON - VOI 2012 Robocon

Tác giả: flashmt

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

char a[505][505],f[2][2][505][1010];
int n,ans=2000;

int main()
{
	int k,x,y,z=0;
	cin >> n >> k;
	while (k--) scanf("%d%d",&x,&y), a[x][y]=1;
	
	for (int i=1;i<=n && !a[1][i];i++) f[0][0][i][i-1]=1;
	for (int i=n;i && !a[1][i];i--) f[1][0][i][n-i]=1;
	
	for (int i=2;i<=n && i-1<ans;i++)
	{
		z^=1;
		for (int j=1;j<=n;j++)
			for (int k=0;k<=i*2;k++)
				f[0][z][j][k]=f[1][z][j][k]=0;
		
		for (int j=1;j<=n;j++)
			if (!a[i][j])
				for (int k=i-1;k<ans && k<=i+j-2;k++)
					f[0][z][j][k]=f[0][1-z][j-1][k-1] | f[0][1-z][j][k-1] | f[0][z][j-1][k-1];
		
		for (int j=n;j;j--)
			if (!a[i][j])
				for (int k=i-1;k<ans && k<=i-1+n-j;k++)
				{
					f[1][z][j][k]=f[1][1-z][j+1][k-1] | f[1][1-z][j][k-1] | f[1][z][j+1][k-1];
					if (f[1][z][j][k] && f[0][z][j][k]) ans=k;
				}
	}
	
	cout << ans << endl;
}

Download