# 11999: 【原1999】二哥找宝箱

### 题目描述

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

## 样例输入

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


## 样例输出

12


## 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();
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>
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;
}