HDU 1072 Nightmare

悠悠 2022-04-16 05:54 136阅读 0赞

## 原题目链接[HDU1072][] ##

--------------------

## 分类 ##

HDU BFS DFS 搜索 剪枝

--------------------

## 题意 ##

走迷宫，并有炸到限时，初始值是6秒，为0秒时爆炸，每走一步消耗一秒，如果能在最短的时间内走出来输出最短的时间，否则输出-1。

0代表墙、1代表路、2代表起点、3代表终点，4代表时间重置

--------------------

## 样例输入输出 ##

Sample Input

3
    3 3
    2 1 1
    1 1 0
    1 1 3
    4 8
    2 1 1 0 1 1 1 0
    1 0 4 1 1 0 4 1
    1 0 0 0 0 0 0 1
    1 1 1 4 1 1 1 3
    5 8
    1 2 1 1 1 1 1 4 
    1 0 0 0 1 0 0 1 
    1 4 1 0 1 1 0 1 
    1 0 0 0 0 3 0 1 
    1 1 4 1 1 1 1 1

Sample Output

4
    -1
    13

--------------------

## 想法 ##

DFS，BFS都可，但想法不同，(不知道为什么，可能是我太菜了,我dfs用bfs的剪枝方法，即炸弹位置只能走一次，错了)；  
**两种方法都需理解一点：**  
同一个炸弹位置当第二次走到时说明已不是最优解。  
**BFS法：**  
处理走到同一个炸弹位置方法：第一次走到炸弹的位置时，将该炸弹设置为0（即墙），将不会再一次走到此处。  
然后就是BFS了。++比DFS慢，因为会走一些重复的++  
**DFS法：**  
记忆化搜索。  
记录走过该点的时间与炸弹剩余爆炸时间。  
然后去掉同样走到该位置时所用时间更久和剩余爆炸时间更短的路。

--------------------

## 代码 ##

BFS(不太会用)

#include<bits/stdc++.h>
    using namespace std;
    const int maxn =  1111;
    const int INF = 0x3f3f3f3f; 
    int n,m,MIN,sx,sy;
    
    int Map[11][11];
    int xx[4] = { 0,1,0,-1};
    int yy[4] = { 1,0,-1,0};
    struct position{ 
    	int x,y,step,t;
    }pos;
    
    int bfs(){ 
    	queue<position> q;
    	q.push(pos);
    	while(!q.empty()){ 
    		pos = q.front();
    		q.pop();
    		for(int i=0;i<4;i++){ 
    			position p;
    			p.x = pos.x+xx[i];
    			p.y = pos.y+yy[i];
    			p.step = pos.step+1;
    			p.t = pos.t-1;
    			if(p.x>=1&p.x<=n&&p.y>=1&&p.y<=m&&Map[p.x][p.y]!=0&&p.t>0){ 
    				if(Map[p.x][p.y]==3){ 
    					return p.step;
    				}
    				if(Map[p.x][p.y]==4){ //重新计时，并且设置为墙，因为下一次到这一定不是最优解 
    					p.t = 6;
    					Map[p.x][p.y] = 0;
    				}
    				q.push(p);
    			}
    		}
    	}
    	return -1;
    }
    int main() { 
    	freopen("in.txt","r",stdin);
    	int T;
    	cin >> T;
    	while(T--){ 
    		scanf("%d%d",&n,&m);
    		for(int i=1;i<=n;i++){ 
    			for(int j=1;j<=m;j++){ 
    				scanf("%d",&Map[i][j]);
    				if(Map[i][j]==2){ 
    					pos.x=i;
    					pos.y=j;
    					pos.step=0;
    					pos.t=6;
    					Map[i][j] = 0;//设置为墙，因为下一次回到起点一定不是最优解 
    				}
    			}
    		}
    		printf("%d\n",bfs()); 
    	}
    	return 0;
    }

DFS(就是递归，经常用)

#include<bits/stdc++.h>
    using namespace std;
    const int maxn =  1111;
    const int INF = 0x3f3f3f3f; 
    int n,m,MIN,sx,sy;
    
    int dis[11][11],Time[11][11];//记忆化搜索，用以判断是否走过 
    int Map[11][11];
    int xx[4] = { 0,1,0,-1};
    int yy[4] = { 1,0,-1,0};
    void dfs(int x,int y,int step,int t){ 
    	if(t == 0||step > MIN) return ;//这里小于0和小于等于0是不一样的，错了几次 
    	if(Map[x][y]==4) t=6;//走到炸弹，可以重置时间为6秒 
    	if(Map[x][y]==3) { //走到终点 
    		if(step<MIN) MIN = step;
    		return;
    	}
    	if(step>=dis[x][y]&&t<=Time[x][y]) return ;//重点，如果当前位置我之前走过，
    						//而且我当前步数比之前走的时候多并且剩余时间比之前少，就没必要继续了 
    	dis[x][y] = step;
    	Time[x][y] = t;
    	for(int i=0;i<4;i++){ 
    		int nx = x+xx[i];
    		int ny = y+yy[i];
    		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&Map[nx][ny]!=0)
    			dfs(nx,ny,step+1,t-1);
    	}
    }
    
    int main() { 
    	freopen("in.txt","r",stdin);
    	int T;
    	cin >> T;
    	while(T--){ 
    		scanf("%d%d",&n,&m);
    		for(int i = 1;i<=n;i++){ 
    			for(int j=1;j<=m;j++){ 
    				scanf("%d",&Map[i][j]);
    				dis[i][j] = INF;
    				Time[i][j]= 0;
    				if(Map[i][j]==2){ 
    					sx = i;
    					sy = j;
    				}
    			}
    		}
    		MIN = INF;
    		dfs(sx,sy,0,6);
    		if(MIN==INF) printf("-1\n");
    		else printf("%d\n",MIN);
    	}
    	return 0;
    }

[HDU1072]: http://acm.hdu.edu.cn/showproblem.php?pid=1072