Skip to content

11999: 【原1999】二哥找宝箱

题目

题目描述

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

题目描述

作为一个强迫症患者，二哥在走游戏里的迷宫时一定要把所有的宝箱收集齐才肯罢休。

现在给你一个\(N \times M\)的迷宫，里面有障碍、空地和宝箱，二哥在某个起始点，每一步二哥可以往上下左右走， 当然前提时没有走出迷宫并且走到的点不是障碍。如果二哥走到了某个为宝箱的点，那么这个宝箱就被他收集到了，然后此处变为空地。

现在你需要计算二哥最少需要走多少步才能收集齐所有的宝箱。

输入格式

输入共有两行。

第一行一个两个正整数N和M，表示迷宫大小。

接下来N行，每行M个整数，第i+1行的第j个整数表示迷宫第i行第j列的情况，0表示空地，-1表示障碍，1表示宝箱，2表示二哥的起始点。保证2只有一个。

输出格式

一行，包含一个整数，表示二哥最少的步数。如果二哥无法收集齐所有宝箱，输出-1。

数据范围

对于全部数据：N，M不超过100，宝箱的个数不超过5。 对于30%的数据，宝箱个数只有1个。

样例输入

3 5
1 -1 1 -1 2
0 -1 0 -1 0
0 0 0 0 0

样例输出

12

限制

时间限制：500ms，内存限制：30000kb

ligongzzz's solution 

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

template <class T>
class my_queue {
public:
    T queue_[50000];
    int start = 0, end = 0;
    int mod = 50000;
    void clear() {
        start = 0;
        end = 0;
        memset(queue_, 0, sizeof(queue_));
    }
    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;
    }
    int size() {
        return end - start;
    }
};

class position {
public:
    int distance = 0;
    int pos_x = 0, pos_y = 0;

    position() = default;
    position(int dis,int x,int y):distance(dis),pos_x(x),pos_y(y){}
};

int map_data[109][109] = { 0 };

bool visited[109][109] = { 0 };
int distance_data[8][109][109] = { 0 };

int dx[] = { 0,1,0,-1 },
dy[] = { 1,0,-1,0 };

int n, m;

my_queue<position> queue_data;
void bfs(int start_x, int start_y, int step) {
    queue_data.clear();
    memset(visited, 0, sizeof(visited));
    position start_point(0, start_x, start_y);
    queue_data.push(start_point);
    visited[start_x][start_y] = true;

    while (!queue_data.empty()) {
        auto temp = queue_data.front();
        queue_data.pop();
        distance_data[step][temp.pos_x][temp.pos_y] = temp.distance;
        for (int i = 0; i < 4; ++i) {
            if (temp.pos_x + dx[i] >= 0 && temp.pos_x + dx[i] < n &&
                temp.pos_y + dy[i] >= 0 && temp.pos_y + dy[i] < m &&
                !visited[temp.pos_x + dx[i]][temp.pos_y + dy[i]]
                && map_data[temp.pos_x + dx[i]][temp.pos_y + dy[i]] != -1) {
                position next_point(temp.distance + 1, temp.pos_x + dx[i], temp.pos_y + dy[i]);
                queue_data.push(next_point);
                visited[next_point.pos_x][next_point.pos_y] = true;
            }
        }
    }
}

bool dfs_visited[10] = { 0 };
int box[8][2] = { 0 };
int box_num = 0;
int dfs(int step, int cur_num) {
    if (cur_num == box_num)
        return 0;
    dfs_visited[step] = true;
    int ans = 10000009;
    for (int i = 1; i <= box_num; ++i) {
        if (!dfs_visited[i]) {
            if (distance_data[step][box[i][0]][box[i][1]] == 0) {
                return -1;
            }
            int cur_ans = dfs(i, cur_num + 1);
            if (cur_ans < 0)
                return -1;
            cur_ans += distance_data[step][box[i][0]][box[i][1]];
            ans = cur_ans < ans ? cur_ans : ans;
        }
    }
    dfs_visited[step] = false;
    return ans;
}

int main() {
    scanf("%d %d", &n, &m);

    int start_x = 0, start_y = 0;


    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &map_data[i][j]);
            if (map_data[i][j] == 2) {
                start_x = i;
                start_y = j;
            }
            else if (map_data[i][j] == 1) {
                box[box_num + 1][0] = i;
                box[box_num + 1][1] = j;
                ++box_num;
            }
        }
    }

    bfs(start_x, start_y, 0);
    for (int i = 1; i <= box_num; ++i)
        bfs(box[i][0], box[i][1], i);

    cout << dfs(0, 0);

    return 0;
}

Neight99's solution 

#include <iostream>

using namespace std;

const int maxN = 1e3 + 10;
const int maxD = 1e9;

template <class elemType>
class seqQueue {
   private:
    elemType *data;
    int maxSize;
    int front, rear;
    void doubleSpace();

   public:
    seqQueue(int size = 1000000);
    ~seqQueue();
    bool isEmpty() const;
    void enQueue(const elemType &);
    elemType deQueue();
    elemType getHead() const;
    int length() const;
};

template <class elemType>
void seqQueue<elemType>::doubleSpace() {
    elemType *tmp = data;
    data = new elemType[maxSize * 2];

    for (int i = 1; i <= maxSize; i++) {
        data[i] = tmp[(front + i) % maxSize];
    }

    front = 0;
    rear = maxSize;
    maxSize *= 2;
    delete[] tmp;
}

template <class elemType>
seqQueue<elemType>::seqQueue(int size) : maxSize(size), front(0), rear(0) {
    data = new elemType[size];
}

template <class elemType>
seqQueue<elemType>::~seqQueue() {
    delete[] data;
}

template <class elemType>
bool seqQueue<elemType>::isEmpty() const {
    return front == rear;
}

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x) {
    if ((rear + 1) % maxSize == front) {
        doubleSpace();
    }
    rear = (rear + 1) % maxSize;
    data[rear] = x;
}

template <class elemType>
elemType seqQueue<elemType>::deQueue() {
    front = (front + 1) % maxSize;
    return data[front];
}

template <class elemType>
elemType seqQueue<elemType>::getHead() const {
    return data[(front + 1) % maxSize];
}

template <class elemType>
int seqQueue<elemType>::length() const {
    return ((rear + maxSize - front) % maxSize);
}

struct Point {
    int x;
    int y;
    int sum;

    Point(int a = 0, int b = 0, int s = 0) : x(a), y(b), sum(s) {}
};

int N, M, boxNum = 0, ans = maxD;
int maze[maxN][maxN] = {0}, note[10][10] = {0}, x0, y0, dx[4] = {-1, 1, 0, 0},
    dy[4] = {0, 0, -1, 1};
Point box[10];
bool isVisited[maxN][maxN] = {0}, choose[10] = {0};

int BFS(int x0, int y0, int x1, int y1);
void DFS(int i, int times, int sum);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N + 2; i++) {
        for (int j = 0; j < M + 2; j++) {
            if (i == 0 || j == 0 || i == N + 1 || j == M + 1) {
                maze[i][j] = -1;
            } else {
                cin >> maze[i][j];
                if (maze[i][j] == 2) {
                    maze[i][j] = 0;
                    box[0] = Point(i, j);
                } else if (maze[i][j] == 1) {
                    box[++boxNum] = Point(i, j);
                }
            }
        }
    }

    for (int i = 0; i <= boxNum; i++) {
        for (int j = i + 1; j <= boxNum; j++) {
            int temp = BFS(box[i].x, box[i].y, box[j].x, box[j].y);
            note[i][j] = note[j][i] = temp;
        }
    }

    DFS(0, boxNum, 0);

    if (ans == maxD) {
        cout << -1;
    } else {
        cout << ans;
    }

    return 0;
}

int BFS(int x0, int y0, int x1, int y1) {
    seqQueue<Point> que;

    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= M + 1; j++) {
            isVisited[i][j] = 0;
        }
    }

    isVisited[x0][y0] = 1;
    que.enQueue(Point(x0, y0, 0));

    while (!que.isEmpty()) {
        Point p = que.deQueue();

        for (int i = 0; i < 4; i++) {
            int x2 = p.x + dx[i], y2 = p.y + dy[i];
            if (x2 == x1 && y2 == y1) {
                return p.sum + 1;
            }
            if (!isVisited[x2][y2] && !maze[x2][y2]) {
                isVisited[x2][y2] = 1;
                que.enQueue(Point(x2, y2, p.sum + 1));
            }
        }
    }

    return maxD;
}

void DFS(int i, int times, int sum) {
    if (sum > ans) {
        return;
    } else if (times == 0) {
        ans = sum;
        return;
    } else {
        for (int j = 1; j <= boxNum; j++) {
            if (!choose[j] && note[i][j] != maxD) {
                choose[j] = 1;
                DFS(j, times - 1, sum + note[i][j]);
                choose[j] = 0;
            }
        }
    }
}

yyong119's solution 

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAX_N 105
#define MAX_M 105
#define MAX_T 6
using namespace std;

struct node {
    int x, y, steps;
    node() : x(0), y(0), steps(0) {}
    node(int p, int q) : x(p), y(q), steps(0) {}
    node(int p, int q, int t) : x(p), y(q), steps(t) {}
}pos_t[MAX_T], st;
const int steps[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m, nums, path_dist, ans = 0x3fff3fff;
int a[MAX_N][MAX_M];
int dist[MAX_T][MAX_T];
bool vis[MAX_T];
bool flag, sol = false;

int find_min_dist(node p, node q) {
    queue<node> que; que.push(p);
    bool vis[MAX_N][MAX_M];
    memset(vis, false, sizeof(vis));
    vis[p.x][p.y] = true;

    while (!que.empty()) {
        node cur = que.front(); que.pop();
        for (int i = 0; i < 4; ++i) {
            node next(cur.x + steps[i][0], cur.y + steps[i][1], cur.steps + 1);
            if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m &&
                        a[next.x][next.y] != -1 && !vis[next.x][next.y]) {
                if (next.x == q.x && next.y == q.y)
                    return next.steps;
                que.push(next);
                vis[next.x][next.y] = true;
            }
        }
    }
    return 0x3fff3fff;
}

void dfs(int idx, int depth, int d) {
    if (depth == nums) {
        path_dist = min(path_dist, d);
        flag = true;
        return;
    }
    for (int i = 0; i < nums; ++i)
        if (!vis[i]) {
            vis[i] = true;
            dfs(i, depth + 1, d + dist[idx][i]);
            vis[i] = false;
        }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 1) {
                pos_t[nums].x = i; pos_t[nums++].y = j;
            }
            if (a[i][j] == 2) {
                st.x = i; st.y = j;
            }
        }
    for (int i = 0; i < nums - 1; ++i)
        for (int j = 0; j < nums; ++j) {
            if (i == j) continue;
            dist[i][j] = find_min_dist(pos_t[i], pos_t[j]);
            dist[j][i] = dist[i][j];
        }
    for (int i = 0; i < nums; ++i) {
        int length1 = find_min_dist(st, pos_t[i]);
        if (length1 == 0x3fff3fff) continue;
        memset(vis, false, sizeof(vis));
        path_dist = 0x3fff3fff;
        vis[i] = true;
        flag = false;
        dfs(i, 1, 0);
        if (flag) {
            ans = min(ans, length1 + path_dist);
            sol = true;
        }
    }
    if (sol)
        printf("%d\n", ans);
    else
        printf("%d\n", -1);
    return 0;
}