Nightmare HDU1072

#include<bits/stdc++.h>using namespace std;int sx,sy,ex,ey;int d[100][100],a[100][100],d2[100][100];bool f[100][100];int n,m;struct aa{ ???int x; ???int y; ???int oil; ???aa(int x=0,int y=0,int oil=0):x(x),y(y),oil(oil){}};void bfs(){ ???const ?int dr[4]={-1,0,1,0}; ???const ?int dc[4]={0,1,0,-1}; ??????queue<aa>q; ???????memset(d,-1,sizeof(d)); ???????memset(f,true,sizeof(f)); ???????aa u(sx,sy,6);d[sx][sy]=0; ???????q.push(u); ??????// printf("u:%d %d %d\n",u.x,u.y,u.oil); ???????while(!q.empty()) ???????{ ???????????aa u=q.front();q.pop(); ???????????if(u.x==ex&&u.y==ey) {printf("%d\n",d[ex][ey]);return;} ???????????for(int i=0;i<=3;i++) ???????????{ ???????????????aa v(u.x+dr[i],u.y+dc[i],u.oil-1); ???????????????d[v.x][v.y]=d[u.x][u.y]+1; ????????????????if(v.x<1||v.x>n||v.y<1||v.y>m) continue ; ???????????????if(v.oil==0)continue ; ???????????????if(a[v.x][v.y]==4){ ??v.oil=6; a[v.x][v.y]=0; ????q.push(v); ?????} ???????????????if(a[v.x][v.y]!=0) ???????????????{ ???????????????????//printf("v:%d %d %d\n",v.x,v.y,v.oil); ????????????????????q.push(v);} ???????????} ???????} ???????printf("-1\n");}int main(){ ???int cas;cin>>cas; ???while(cas--) ???????{ ???????cin>>n>>m; ???????for(int i=1;i<=n;i++) ???????????for(int j=1;j<=m;j++) ?????????????{ ???????????????scanf("%d",&a[i][j]); ???????????????if(a[i][j]==2){sx=i;sy=j;} ???????????????if(a[i][j]==3){ex=i;ey=j;} ?????????????} ????????????bfs(); ???} ???return 0;}

#include <iostream>#include <algorithm>#include <queue>#include <memory.h>#include <stdio.h>using namespace std;#define Size 8/* ???这题目可以重复道路.只需要把控制炸弹的地方使用后,变成墙壁即可.*/struct Node{ ???int x; ???int y; ???int time;//time代表已用的时间. ???int rest;//rest代表剩余的时间. ???//按照时间从高到低排列. ???bool operator < (Node a) const ???{ ???????return this->time > a.time; ???}};int world[Size][Size];int n, m;int temp;int dir[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };int sx, sy;int rx, ry;/* ???0代表墙壁.1代表正常路.2代表起点.3代表终点.4代表炸弹控制器.*/int bfs(){ ???priority_queue<Node> temp; ???Node now, next, s; ???s.x = sx; ???s.y = sy; ???s.time = 0; ???s.rest = 6; ???temp.push(s); ???while (!temp.empty()) ???{ ???????now = temp.top(); ???????temp.pop(); ???????if (now.x == rx && now.y == ry && now.rest > 0) ???????{ ???????????return now.time; ???????} ???????//减枝.当剩余时间为1时.还没找到出口,说明到不了了. ???????if (now.rest == 1) ???????????continue; ???????for (int i = 0; i < 4; ++i) ???????{ ???????????next.x = now.x + dir[i][0]; ???????????next.y = now.y + dir[i][1]; ???????????next.time = now.time + 1; ???????????next.rest = now.rest - 1; ???????????//判断位置是否合理. ???????????if (next.x >= 0 && next.y >= 0 && next.x < n && ?next.y < m && ?world[next.x][next.y] != 0 && next.rest >= 1) ???????????{ ???????????????//如果他到了炸弹这里. ???????????????if (world[next.x][next.y] == 4) ???????????????{ ???????????????????next.rest = 6; ???????????????????//改为墙壁即可. ???????????????????world[next.x][next.y] = 0; ???????????????} ???????????????temp.push(next); ???????????} ???????} ???} ???return -1;}int main(){ ???int t; ???scanf("%d", &t); ???for (int i = 0; i < t; ++i) ???{ ???????scanf("%d%d", &n,&m); ???????memset(world, 0, sizeof(world)); ???????for (int j = 0; j < n; ++j) ???????{ ???????????for (int k = 0; k < m; ++k) ???????????{ ???????????????scanf("%d", &temp); ???????????????//初始位置. ???????????????if (temp == 2) ???????????????{ ???????????????????sx = j; ???????????????????sy = k; ???????????????} ???????????????//目标位置. ???????????????else if (temp == 3) ???????????????{ ???????????????????rx = j; ???????????????????ry = k; ???????????????} ???????????????world[j][k] = temp; ???????????} ???????} ???????printf("%d\n", bfs()); ???} ???return 0;}