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;
}