Hdu1072广搜
题意：0不能走，1可以走，2起始位置，3中点，4时间变成6.初始时间为6 走到终点或者4时时间不能为0.问能否走到终点和 到终点的最短距离。
反正时间就是6 ，每个点可以重复走，随便走就行。剪纸 就是 经过4这个点只要经过一次，第二次经过这个点的路程一定比第一次经过的长 并且都重置了时间。
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <vector> #include <map> #include <string> #include <iostream> using namespace std; const int maxn = 8; int Map[maxn][maxn]; int n,m; int bx,ex,by,ey; int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; struct Node { int x;int y;int time;int dist; }; int gao(int x,int y) { if(x>=0&&x<n&&y>=0&&y<m&&Map[x][y]) return 1; return 0; } int dfs() { queue<Node> q; Node t ; t.x= bx;t.y=by; t.time= 6; t.dist= 0; q.push(t); while(!q.empty()){ Node cur=q.front(); q.pop(); if(cur.x==ex&&cur.y==ey) return cur.dist; if(cur.time<=1) continue; for(int i=0;i<4;i++){ int xx= cur.x+dx[i];int yy=cur.y+dy[i]; if(!gao(xx,yy)) continue; Node gg; gg.x= xx ;gg.y= yy; gg.dist= cur.dist+1; gg.time = cur.time- 1; if(Map[xx][yy]==4){ Map[xx][yy]=0;gg.time = 6; } q.push(gg); } } return -1; } int main() { int Icase; cin>>Icase; while(Icase--){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&Map[i][j]); if(Map[i][j] ==2) bx = i ,by = j; if(Map[i][j]==3) ex = i ,ey = j; } } printf("%d ",dfs()); } return 0; }