Problem Description

作為一個強迫癥患者，小 Y 在走游戲里的迷宮時一定要把所有的寶箱收集齊才肯罷休。現在給你一個 N *M 的迷宮，里面有障礙、空地和寶箱，小 Y 在某個起始點，每一步小 Y 可以往上下左右走，當然前提時沒有走出迷宮并且走到的點不是障礙。如果小 Y 走到了某個為寶箱的點，那么這個寶箱就被他收集到了，然后此處變為空地。 現在你需要計算小 Y 最少需要走多少步才能收集齊所有的寶箱。

Input

輸入包含多組數據。 對于每組數據，第一行兩個正整數 N;M(1<=N;M<=100)，表示迷宮大小。 接下來 N 行，每行 M 個整數，第 i + 1 行的第 j 個整數表示迷宮第 i 行第 j 列的情況，0 表示空地，-1表示障礙，1 表示寶箱，2 表示小Y 的起始點。保證2 只有一個，且寶箱數量不超過5 個。 數據以兩個0 表示結尾。

Output

對于每組數據輸出一行，包含一個整數，表示小 Y 最少的步數。如果小 Y 無法收集齊所有寶箱，輸出-1。

Sample Input

3 5 1 -1 1 -1 2 0 -1 0 -1 0 0 0 0 0 0 0 0
#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
int map[105][105];
int ss[105][105];
int sr[8][8];
int m,n,cnt;
int dir[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
bool isarea(int x,int y)
{
?return x>=0&&x<m&&y>=0&&y<n;
}
struct ff{
?int x;
?int y;
};
ff f1[8];
struct lmx{
?int x;
?int y;
?int step;
};
int bfs(int e,int w)
{
?? queue<lmx>q;
?? while(!q.empty()) q.pop();
?? int i,j;
?? for(i=0;i<m;i++)
?? {
??? for(j=0;j<n;j++)
??? {
???? map[i][j]=ss[i][j];
??? }
?? }
?? lmx s1,s2,s3;
?? s1.x=f1[e].x;
?? s1.y=f1[e].y;
?? s1.step=0;
?? q.push(s1);
?? map[s1.x][s1.y]=-1;
?? while(!q.empty())
?? {
????? s2=q.front();
?? q.pop();
????? for(i=0;i<4;i++)
?? {
????????? s3.x=s2.x+dir[i][0];
??? s3.y=s2.y+dir[i][1];
??? if(map[s3.x][s3.y]!=-1&&isarea(s3.x,s3.y))
??? {
?????? s3.step=s2.step+1;
???????????????? q.push(s3);
???? map[s3.x][s3.y]=-1;
????? if(f1[w].x==s3.x&&f1[w].y==s3.y) return s3.step;
??? }
?? }
?? }
?? return -1;
}
int main()
{
???? int i,j,flag,sum,ce;
???? char sp[7]={"012345"};
? while(cin>>m>>n)
? {
?? cnt=1;
?? ce=10000;
?? sum=0;
?? flag=0;
?? if(m==0&&n==0) break;
?? for(i=0;i<m;i++)
?? {
??? for(j=0;j<n;j++)
??? {
???? cin>>ss[i][j];
???? if(ss[i][j]==2)? {f1[0].x=i;f1[0].y=j;}
???? if(ss[i][j]==1)? {f1[cnt].x=i;f1[cnt].y=j;cnt++;}
??? }
?? }
?? memset(sr,0,sizeof(sr));
?? for(i=0;i<cnt;i++)
?? {
??? for(j=0;j<cnt;j++)
??? {
???? if(i!=j) sr[i][j]=bfs(i,j);
???? if(sr[i][j]<0) { flag=1;break;}
??? }
??? if(flag) break;
?? }
?? if(flag)cout<<"-1"<<endl;
?? else
?? {
??? do{
???? sum=0;
???? for(i=0;i<cnt-1;i++)
???? {
??????? sum+=sr[sp[i]-'0'][sp[i+1]-'0'];
???? }
???? if(sum<ce) ce=sum;
??? }while(next_permutation(sp+1,sp+cnt));
??? cout<<ce<<endl;
?? }
? }
?return 0;
}

轉載于:https://www.cnblogs.com/ffhuguang/archive/2013/03/29/2988202.html

總結

以上是生活随笔為你收集整理的找宝箱的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。