ROBOCON - VOI 2012 Robocon
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<queue>
#define MAX 505
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi first
#define se second
using namespace std;
bool allowCell[MAX][MAX];
bool inQueue[2][2][MAX][MAX];
int n;
int dx[][3]={{0,1,1},{0,1,1}};
int dy[][3]={{1,0,1},{-1,0,-1}};
void init(void) {
int k;
scanf("%d%d",&n,&k);
FOR(i,1,n) FOR(j,1,n) allowCell[i][j]=true;
REP(zz,k) {
int x,y;
scanf("%d%d",&x,&y);
allowCell[x][y]=false;
}
}
bool canMove(int x,int y) {
if (x<1 || x>n || y<1 || y>n) return (false);
return (allowCell[x][y]);
}
void process(void) {
queue<pair<int,int> > q[2][2];
q[0][0].push(make_pair(1,1));
q[0][1].push(make_pair(1,n));
inQueue[0][0][1][1]=true;
inQueue[0][1][1][n]=true;
REP(t,MAX*MAX) {
int curPos=t%2;
int nextPos=curPos^1;
REP(i,2) while (!q[curPos][i].empty()) {
int x=q[curPos][i].front().fi;
int y=q[curPos][i].front().se;
q[curPos][i].pop();
inQueue[curPos][i][x][y]=false;
if (inQueue[curPos][i^1][x][y]) {
printf("%d\n",t);
return;
}
REP(j,3) if (canMove(x+dx[i][j],y+dy[i][j])) {
int tx=x+dx[i][j];
int ty=y+dy[i][j];
if (!inQueue[nextPos][i][tx][ty]) {
inQueue[nextPos][i][tx][ty]=true;
q[nextPos][i].push(make_pair(tx,ty));
}
}
}
}
}
int main(void) {
init();
process();
return 0;
}