12104: 【原2104】大脸上课

题目描述

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

Description

由于dota水平太差被高手排斥，大脸同学最近迷上了打FIFA(虽然踢的依旧很臭)。一天晚上大脸通宵达旦和室友大战了三百回合，早上自然起晚了，可他又十分害怕迟到。

危难时刻，他拿出了自己的GPS，他发现以寝室为原点(坐标为\((0,0)\))，上课教室的坐标为\((X,Y)\)，每个时间单位他可以向东西南北某个方向走一步。如\((0,0)\)可以到达\((0,1),(1,0),(0，-1),(-1,0)\)。

他希望尽快走到教室，然而事情没有这么简单，因为一路上还有许多艰难险阻，比如大脸不会游泳，所以他不可能走到思春湖或者思源湖里(除非他觉得准时到达无望，一怒投湖)。具体来说，有N个障碍，第i个障碍的坐标是\((A_i, B_i)\)。

于是大脸求助于你，请问大脸到达教室需要的最少时间是多少？

Input Format

第一行，三个整数\(X,Y,N\)。第\(2 \cdots N+1\)行，第\(i+1\)行两个整数\((Ai, Bi)\)。

Output Format

一行一个整数，表示大脸需要的最少时间。

Sample Input

About Sample Input

教室的坐标是\((1, 2)\). 障碍物是\((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

About Sample Output

*代表大脸的最佳线路。

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

3 * M . * . . . .

2 * . M C M . M .

1 * M . M . M . .

0 ***** . . . . .

-1 . . . . . . . .

  -2-1 0 1 2 3 4 5

About Testdata

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