//迷宫求解的变形:广度优先搜索//关键解决重复回路问题#include <iostream>using namespace std;int n,m;int map[10][10];int mark[10][10]; //该地的剩余时间int sj,sk,ej,ek;int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //遍历的四个方向int mintime =0;typedef struct node{ int x; int y; int step; int time;}node;node myqueue[100]; //维持广度优先搜索中的队列void BFS(){ int i,j; memset(mark,0,sizeof(mark)); int start = 0; int end =1; myqueue[0].x = sj; myqueue[0].y = sk; myqueue[0].step = 0; myqueue[0].time = 6; node frontnode,nextnode; while(end!=start) { frontnode = myqueue[start]; start++; //在进行四个方向遍历时考虑(1)是否值得加入到队列中(判断当前剩余时间与该点剩余时间)(2)是否是出口(3)是否是炸弹重置器 for(i=0;i<4;++i) { nextnode.x = frontnode.x + dir[i][0]; nextnode.y = frontnode.y + dir[i][1]; nextnode.step = frontnode.step+1; nextnode.time = frontnode.time-1; if(nextnode.time <= mark[nextnode.x][nextnode.y]) //本题的关键：是否值得加入到队列中(判断当前剩余时间与该点剩余时间)，从而解决重复回路问题 continue; if(nextnode.time>0 && nextnode.x>=0 && nextnode.x < n && nextnode.y >=0 && nextnode.y<m && map[nextnode.x][nextnode.y]!=0) { if(map[nextnode.x][nextnode.y] == 3) { mintime = nextnode.step; return; } else if(map[nextnode.x][nextnode.y]==4) nextnode.time = 6; mark[nextnode.x][nextnode.y] = nextnode.time; myqueue[end] = nextnode; end++; } } }}int main(){ //freopen("1.txt","r",stdin); int t; int i,j,k; cin>>t; for(i=0;i<t;++i) { cin>>n>>m; for(j=0;j<n;++j) { for(k=0;k<m;++k) { cin>>map[j][k]; if(map[j][k]==2) { sj = j; sk = k; } } } mintime = 0; //记录所用的最小时间 BFS(); if(mintime>0) cout<<mintime<<endl; else cout<<-1<<endl; } return 0;}
转载于:https://www.cnblogs.com/north_dragon/archive/2010/05/04/1727159.html
