ROBOCON - VOI 2012 Robocon

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 505;
const int NN = 15 * N * N;
const int dx1[] = {0, 1, 1};
const int dy1[] = {1, 1, 0};
const int dx2[] = {0, 1, 1};
const int dy2[] = {-1, -1, 0};

using namespace std;
II Q1[NN], Q2[NN];
bool block[N][N], was1[N][N], was2[N][N];
int n, k, l1, r1, l2, r2;

bool out(II u)
    {return u.X < 1 || u.Y < 1 || u.X > n || u.Y > n || block[u.X][u.Y];}

void bfs1() {
    int tmp = r1;
    while (l1 <= r1) {
        II u = Q1[l1++];
        FOR(i, 0, 3) {
            II v (u.X + dx1[i], u.Y + dy1[i]);
            if (out(v)) continue;
            if (!was1[v.X][v.Y]) {
                was1[v.X][v.Y] = 1;
                Q1[++tmp] = v;
            }
        }
    }
    r1 = tmp;
}


bool bfs2() {
    int tmp = r2;
    while (l2 <= r2) {
        II u = Q2[l2++];
        FOR(i, 0, 3) {
            II v (u.X + dx2[i], u.Y + dy2[i]);
            if (out(v)) continue;
            if (was1[v.X][v.Y]) return true;
            if (!was2[v.X][v.Y]) {
                was2[v.X][v.Y] = 1;
                Q2[++tmp] = v;
            }
        }
    }
    r2 = tmp;
    return false;
}


int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    int u, v;
    FOR(i, 0, k) {
        cin >> u >> v;
        block[u][v] = 1;
    }
    l1 = r1 = 1; Q1[1] = II(1, 1);
    l2 = r2 = 1; Q2[1] = II(1, n);
    FOR(step, 1, n * n) {
        bfs1();
        if (bfs2()) {cout << step; break;}
        REP(i, l1, r1) was1[Q1[i].X][Q1[i].Y] = 0;
        REP(i, l2, r2) was2[Q2[i].X][Q2[i].Y] = 0;
    }
    return 0;
}

Download