本文主要是介绍小明的迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Accept: 65 Submit: 196
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
小明误入迷宫，塞翁失马焉知非福，原来在迷宫中还藏着一些财宝，小明想获得所有的财宝并离开迷宫。因为小明还是学生，还有家庭作业要做，所以他想尽快获得所有财宝并离开迷宫。
Input
有多组测试数据。
每组数据第一行给出两个正整数n,m(0<n,m<=100)。代表迷宫的长和宽。
接着n行，每行m个整数。正数代表财宝(财宝的个数不超过10)；负数代表墙，无法通过；0代表通道。
每次移动到相邻的格子，所花费的时间是1秒。小明只能按上、下、左、右四个方向移动。
小明的初始位置是（1,1）。迷宫的出口也在（1,1）。
Output
输出获得所有财宝并逃出迷宫所花费的最小时间，如果无法完成目标则输出-1。
Sample Input
3 30 0 00 100 00 0 02 21 11 1
Sample Output
44
Source
状态压缩dp
bfs求各点之间的最短路，最后是旅行商问题。
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdio>
#include <queue>
#include <cstring>using namespace std;const int INF = 10000000;
const int MAXN = 100 + 2;
int mt[MAXN][MAXN];
int pos[MAXN][MAXN];
int n, m, num;
int arr[10 + 1];
int dis[10 + 1][10 + 1];
int dp[2048 + 10][11 + 1];struct Node
{int x, y;int pos;int dis;bool operator < (const Node a) const{return pos < a.pos;}
}money[10 + 1];bool vis[MAXN][MAXN];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
queue <Node> q;void bfs(int x)
{Node cur, next;memset(vis, false, sizeof(vis));cur = money[x];cur.dis = 0;vis[cur.x][cur.y] = true;q.push(cur);while (!q.empty()){cur = q.front();q.pop();if (mt[cur.x][cur.y] > 0) dis[x][pos[cur.x][cur.y]] = dis[pos[cur.x][cur.y]][x] = cur.dis;for (int i = 0; i < 4; i++){next.x = cur.x + dir[i][0], next.y = cur.y + dir[i][1];if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m){if (mt[next.x][next.y] != -1 && vis[next.x][next.y] == false){vis[next.x][next.y] = true;next.dis = cur.dis + 1;q.push(next);}}}}
}void input()
{while (scanf("%d %d", &n, &m) != EOF){num = 0;money[0].x = 0;money[0].y = 0;money[0].pos = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){scanf("%d", &mt[i][j]);pos[i][j] = 0;if (mt[i][j] > 0){num++;money[num].x = i;money[num].y = j;money[num].pos = num;pos[i][j] = num;}}}if (mt[0][0] == -1){printf("-1\n");continue;}for (int i = 0; i <= num; i++){for (int j = 0; j <= num; j++){dis[i][j] = (i == j ? 0 : INF);}}for (int i = 1; i <= num; i++) arr[i] = i;for (int i = 0; i <= num; i++) bfs(i);long long ans = INF, temp = 0;for (int i = 0; i < 2048 + 10; i++){for (int j = 0; j < 11 + 1; j++) dp[i][j] = INF;}dp[0][0] = 0;for (int i = 0; i < 1 << (num + 1); i++){for (int j = 0; j < num + 1; j++){for (int k = 0; k < num + 1; k++){if ((i & (1 << j)) == 0){if (dis[j][k] != INF){dp[i | (1 << j)][j] = min(dp[i | (1 << j)][j], dp[i][k] + dis[j][k]);}}}}}if (dp[(1 << (num + 1)) - 1][0] != INF){printf("%d\n", dp[(1 << (num + 1)) - 1][0]);}else{printf("%d\n", -1);}}
}int main()
{input();return 0;
}
这篇关于小明的迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
