# 12104: 【原2104】大脸上课

### 题目描述

author: cby1992 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2104

## Sample Input

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2


4 . . . . . . . .

3 . M . . . . . .

2 . . M C M . M .

1 . M . M . M . .

0 . . * . . . . .

-1 . . . . . . . .

-2-1 0 1 2 3 4 5


## Sample Output

11


*代表大脸的最佳线路。

4 ******* . . . .

3 * M . * . . . .

2 * . M C M . M .

1 * M . M . M . .

0 ***** . . . . .

-1 . . . . . . . .

-2-1 0 1 2 3 4 5


30%的数据，$$-20 \leq Ai, Bi, X, Y \leq 20$$

50%的数据，$$-100 \leq Ai, Bi, X, Y \leq 100$$

100%的数据，$$N\leq 10,000, -500 \leq Ai, Bi, X, Y \leq 500$$

## Limits

Time limit: 1000ms, memory limit: 131072kb.

## FineArtz's solution

/* 大脸上课 */
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int D = 502;

bool v[1005][1005];

int lBound = 0, rBound = 1005, uBound = 1005, dBound = 0;

class Point{
public:
Point() = default;
Point(int xx, int yy) : x(xx), y(yy), step(0) {}
int x = 0, y = 0, step = 0;
};

bool check(const Point &p){
if (p.x < lBound || p.x > rBound || p.y < lBound || p.y > uBound || v[p.x][p.y]) return false;
else return true;
}

int main(){
memset(v, 0, sizeof(v));
v[D][D] = true;
int x, y, n;
cin >> x >> y >> n;
x += D;
y += D;
/*lBound = min(lBound, x - 1);
rBound = max(rBound, x + 1);
uBound = max(uBound, y + 1);
dBound = min(dBound, y - 1);*/
for (int i = 1; i <= n; ++i){
int a, b;
cin >> a >> b;
a += D;
b += D;
v[a][b] = true;
/*lBound = min(lBound, a - 1);
rBound = max(rBound, a + 1);
uBound = max(uBound, b + 1);
dBound = min(dBound, b - 1);*/
}
queue<Point> q;
Point s(D, D);
q.push(s);
while (!q.empty()){
Point now = q.front(), next;
q.pop();
if (now.x == x && now.y == y){
cout << now.step << endl;
return 0;
}
for (int i = 0; i != 4; ++i){
next.x = now.x + dx[i];
next.y = now.y + dy[i];
next.step = now.step + 1;
if (check(next)){
q.push(next);
v[next.x][next.y] = true;
}
}
}
return 0;
}


## ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

class Position {
public:
int x = 0, y = 0;
int distance = 0;

Position() = default;
Position(int x,int y,int dis):x(x),y(y),distance(dis){}
};

template <class T>
class my_queue {
T queue_[100000];
int start = 0, end = 0;
int mod = 100000;
public:
bool empty() const{
return end - start == 0;
}
T front() const {
return queue_[start % mod];
}
void pop() {
++start;
}

void push(const T& val) {
queue_[(end++) % mod] = val;
}
};

bool map[1209][1209] = { 0 };

int dx[] = { 0,1,0,-1 },
dy[] = { 1,0,-1,0 };
my_queue<Position> queue_data;

int bfs(int destx,int desty) {
Position init_pos(600, 600, 0);
queue_data.push(init_pos);
map[600][600] = true;
while (!queue_data.empty()) {
auto temp = queue_data.front();
queue_data.pop();

//判断是否到达
if (temp.x == destx && temp.y == desty)
return temp.distance;
for (int i = 0; i < 4; ++i) {
if (temp.x + dx[i] >= 0 && temp.y + dy[i] >= 0 && temp.x + dx[i] <= 1200
&& temp.y + dy[i] <= 1200 && !map[temp.x + dx[i]][temp.y + dy[i]]) {
Position next_pos(temp.x + dx[i], temp.y + dy[i], temp.distance + 1);
queue_data.push(next_pos);
map[next_pos.x][next_pos.y] = true;
}
}
}
return 0;
}

int main() {
int X, Y, N;
cin >> X >> Y >> N;
X += 600;
Y += 600;

for (int i = 0; i < N; ++i) {
int tempx, tempy;
scanf("%d %d", &tempx, &tempy);
map[tempx + 600][tempy + 600] = true;
}

cout << bfs(X, Y);

return 0;
}


## skyzh's solution

#include <iostream>
using namespace std;

bool MAP[2000][2000] = { 0 };
bool visited[2000][2000] = { 0 };

inline bool& map_at(int x, int y) { return MAP[x + 500][y + 500]; }
inline bool& visited_at(int x, int y) { return visited[x + 500][y + 500]; }

struct a_step {
int x, y, step;
};

a_step d[1000000];
int front = 0, rear = 0;

int bfs(int X, int Y) {
d[rear].x = 0;
d[rear].y = 0;
d[rear].step = 0;
++rear;
while (front < rear) {
a_step &current = d[front];
++front;
static int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
for (int _d = 0; _d < 4; _d++) {
int _x = current.x + dir[_d][0];
int _y = current.y + dir[_d][1];
if (_x >= -505 && _y >= -505 && _x <= 505 && _y <= 505) {
if (map_at(_x, _y) == false && visited_at(_x, _y) == false) {
visited_at(_x, _y) = true;
if (_x == X && _y == Y) return current.step + 1;
a_step &tmp = d[rear];
tmp.x = _x;
tmp.y = _y;
tmp.step = current.step + 1;
++rear;
}
}
}
}
return 0;
}

int main() {
int X, Y, N, x, y;
scanf("%d%d%d", &X, &Y, &N);
for (int i = 0; i < N; i++) {
scanf("%d%d", &x, &y);
map_at(x, y) = true;
}
printf("%d\n", bfs(X, Y));
return 0;
}