HDOJ1072 Nightmare（BFS，记忆化搜索，剪枝）

HDOJ1072
这道题可以剪枝：
剪枝说明：如果当前到达该点时间少于该点剩余时间并且步数大于该点步数，则返回.
剪枝说明：http://blog.csdn.net/iaccepted/article/details/23198623

2019年2月21日

很好的一道BFS题目，搜索的过程中记录当前点的搜索状态。开始写的时候错误出现在判断条件，

            //判断是否在范围内，判断是否已经走过if(q2.x<0||q2.x>=n||q2.y<0||q2.y>=m) continue;if(q2.t<=0||a[q2.x][q2.y]==0) continue;

开始边界条件写成了$q2.t<0$。

#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#define maxn 10010
typedef long long ll;
using namespace std;
int T,n,m,sx,sy,ex,ey;
int ans;
typedef struct Node{
    int x,y;int t,step; //记录每个点的剩余时间和走过的步数
}node;
node ss;
int a[maxn][maxn];
int dx[4]={
    -1,0,1,0};
int dy[4]={
    0,1,0,-1};
int bfs(){
    queue<node> que;node q1,q2;que.push(ss);while(!que.empty()){
    q1=que.front();que.pop();for(int i=0;i<4;i++){
    q2.x=q1.x+dx[i];q2.y=q1.y+dy[i];q2.step=q1.step+1;q2.t=q1.t-1;//判断是否在范围内，判断是否已经走过if(q2.x<0||q2.x>=n||q2.y<0||q2.y>=m) continue;if(q2.t<=0||a[q2.x][q2.y]==0) continue;if(a[q2.x][q2.y]==3){
    ans=q2.step;return true;}else if(a[q1.x][q2.y]==4){
    q2.t=6;a[q2.x][q2.y]=0;//标记走过}que.push(q2);}}return false;
}int main(){
    ios::sync_with_stdio(false);cin>>T;while(T--){
    cin>>n>>m;for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
    cin>>a[i][j];if(a[i][j]==2){
    ss.x=i;ss.y=j;ss.step=0;ss.t=6;}}}if(bfs()) {
    cout<<ans<<endl;}else{
    cout<<"-1"<<endl;}}return 0;
}

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
const int N=10;
using namespace std;
int map[N][N],n,m;
int dir[][2]={
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};
struct node{
    int x,y;  //记录坐标int step,time;  //记录步数和时间
}start;
void BFS(){
    queue<node> q;//队列实现node q1,q2;q.push (start);while(!q.empty ()){
    int i;q1=q.front ();q.pop ();for(i=0;i<4;i++){
    q2.x=q1.x+dir[i][0];q2.y=q1.y +dir[i][1];q2.step =q1.step+1;q2.time =q1.time -1;//判断这一步是否超过矩阵的范围//判断这不不是走过的（或墙）或炸弹的时间已到if(q2.x>=0&&q2.y>=0&&q2.x<n&&q2.y<m&&map[q2.x][q2.y]!=0&&q2.time >0){
    //说明找到答案，搜索结束if(map[q2.x][q2.y]==3){
    cout<<q2.step<<endl ;return ;}else if(map[q2.x][q2.y]==4){
    q2.time =6;  //碰到时间调整器，可以恢复时间map[q2.x][q2.y]=0;//标记已经走过}q.push (q2); //将这一步放进队列}}	}//队列搜完都没找到答案，说明答案不存在cout<<"-1"<<endl;return ;
}int main(){
    int i,j,T;scanf("%d",&T);while(T--){
    cin>>n>>m;for(i=0;i<n;i++)for(j=0;j<m;j++){
    cin>>map[i][j];if(map[i][j]==2){
    start.x=i;start.y=j;start.step =0;start.time =6; //时间初始化为6}}BFS();}return 0;
}