ROBOCON - VOI 2012 Robocon
Tác giả: ll931110
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define BLOCK 60
using namespace std;
long long olda[1005][17],newa[1005][17],oldb[1005][17],newb[1005][17],wall[1005][17];
int n,k;
int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) wall[i][j/BLOCK] |= (1LL << (j % BLOCK));
for (int i = 0; i < k; i++) {
int x,y;
scanf("%d %d", &x, &y);
x--; y--;
wall[x][y/BLOCK] ^= (1LL << (y % BLOCK));
}
olda[0][0] = 1;
oldb[0][(n - 1)/BLOCK] = 1LL << ((n - 1) % BLOCK);
for (int ret = 1; ret <= n + n; ret++) {
memset(newa,0,sizeof(newa));
for (int i = 0; i < n; i++)
for (int j = 0; j < 17; j++) {
newa[i][j] |= olda[i][j] << 1;
if (olda[i][j] & (1LL << (BLOCK - 1))) newa[i][j + 1] |= 1;
newa[i][j] %= (1LL << BLOCK);
if (i >= n - 1) continue;
newa[i + 1][j] |= olda[i][j];
newa[i + 1][j] |= olda[i][j] << 1;
if (olda[i][j] & (1LL << (BLOCK - 1))) newa[i + 1][j + 1] |= 1;
newa[i + 1][j] |= (1LL << BLOCK);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < 17; j++) {
newb[i][j] |= oldb[i][j] >> 1;
if (j && (oldb[i][j] & 1)) newb[i][j - 1] |= (1LL << (BLOCK - 1));
if (i >= n - 1) continue;
newb[i + 1][j] |= oldb[i][j];
newb[i + 1][j] |= oldb[i][j] >> 1;
if (j && (oldb[i][j] & 1)) newb[i + 1][j - 1] |= (1LL << (BLOCK - 1));
}
for (int i = 0; i < n; i++)
for (int j = 0; j < 17; j++) {
olda[i][j] = newa[i][j] & wall[i][j];
oldb[i][j] = newb[i][j] & wall[i][j];
if (olda[i][j] & oldb[i][j]) {
printf("%d\n", ret);
return 0;
}
}
}
printf("-1\n");
}