Problem B: DFS or BFS?
題目
Description
說好了，題目不黑人，
給你一個8*8的矩陣，你的初始位置是左下角方格（用’U’表示），你的目標位置是右上角的方格(用’A’表示），其余的62個方格，如果是’.’，表示這個方格為空，如果是’S’，表示這個方格有一塊大石頭，好了現在你開始從左下角出發，每次可以往上，下，左，右，左上，右上，左下，右下移動一個方格，或者你可以原地不動，一共九個動作方式，在你做完一個動作后，所有的大石頭會往下掉一個方格（如果一個大石頭的位置是（x，y）,那下一秒是（x+1，y）,不過如果它已經在最下面的一排了，那它就會掉出矩陣，不再出現），請注意，任一時刻，你不能和某一個大石頭處在同一個方格，否則石頭會把你XX掉，
現在的問題就是：你能從左下角安全抵達右上角么？ 如果能，輸出“Yes”，反之，“No”，
Input
T->測驗資料組數(T)，
對于每組資料，輸入一個8*8的矩陣，其后有一空行，描述如上，
Output
對于第i組資料，請輸出
Case #i: s(s是一個字串，如果可以到達，則s為“Yes”，反之“No”)
Sample Input Copy
2
.......A
........
........
........
........
........
........
U.......
.......A
........
........
........
........
.S......
S.......
US......
Sample Output Copy
Case #1: Yes
Case #2: No
思路
- 本題使用bfs，需要一個佇列來push和pop點從而走迷宮，詳情請見bfs相關知識
- 注意使用states（set）來判斷是否該坐標和當時的bottom的值是否曾經出現過
- 因為bfs是不斷push和pop來保存狀態的
- 所以可能造成到達某一層的A點和B點繼續運動后會同時到達C點，狀況重復
- 與過去的bfs不同的是，本題有每動一次，石頭集體下落一格的特殊要求
- 如果遍歷整個map，會造成非常大的時間復雜度
- 所以比起修改整體的地圖，更好的選擇是切換視角
- 也就是top[2]所做的作業，同時top[2]可以保證點向上運動的趨勢，從而快速達到最終點
- 當達到最上面一行時，一定可以到達終點（只要向左一直走就好），直接return，
代碼
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <set>
#include <queue>
using namespace std;
char map[8][8];
set<vector<int>> states;//用set判斷人物移動后，坐標和bottom的值是否曾經出現過
int flag;
struct point{
int x;
int y;
int step;
};
bool check(int x,int y,int bottom){
//注意判斷其上方是否是一個石頭
if(x>=0&&x<=bottom&&y>=0&&y<8&&map[x][y]!='S'&&map[x-1][y]!='S')
return true;
return false;
}
void bfs(){
states.clear();
states.insert({7,0,7});//插入起始點
queue<vector<int>> Q;//bfs佇列
Q.push({7,0,7});//插入起始點
while(!Q.empty()){//佇列為空，bfs結束
vector<int> top=Q.front();
if(top[2]==0||top[0]==0){
//代表到達最上面一行以上，則安全
flag=true;
return;
}
Q.pop();//彈出，開始處理
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
if(check(top[0]+i,top[1]+j,top[2])&&!states.count({top[0]+i-1,top[1]+j,top[2]-1})){
states.insert({top[0]+i-1,top[1]+j,top[2]-1});//插入新點
Q.push({top[0]+i-1,top[1]+j,top[2]-1});
}
}
}
}
}
int main(){
int n=0;
while(scanf("%d",&n)!=EOF){
for(int k=1;k<=n;k++){
flag=false;
string input;
getline(cin,input);
for(int i=0;i<8;i++){
getline(cin,input);
for(int j=0;j<8;j++){
map[i][j]=input[j];
}
}
bfs();
printf("Case #%d: %s\n", k, flag ? "Yes" : "No");
}
}
return 0;
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/193745.html
標籤：java
上一篇：電子老鼠闖迷宮noj