題目連結: https://tioj.ck.tp.edu.tw/problems/1085
# 內容
給定一個立體 (x * y * z) 的迷宮，某人自 (1,1,1) 走至 (x,y,z)，請求出一條最短路徑，若有多組解，任一組都可
# 解題思路
就是三維的 BFS 阿～～只是要紀錄之前走過的路徑喔！！
# 程式碼
#include<bits/stdc++.h> | |
using namespace std; | |
#define AC ios::sync_with_stdio(0),cin.tie(0); | |
#define PB push_back | |
#define null 2147483647 | |
bool puzzle[55][55][55]; | |
struct point{ | |
char x,y,z; | |
int last,This; | |
}; | |
vector<point> v; | |
int main(){ | |
int x,y,z; | |
scanf("%d%d%d",&x,&y,&z); | |
for(int i=1;i<=z;i++){ | |
for(int j=1;j<=y;j++){ | |
for(int k=1;k<=x;k++){ | |
int b; | |
scanf("%d",&b); | |
puzzle[k][j][i]=!b; | |
} | |
} | |
} | |
if(puzzle[1][1][1]==0 || puzzle[x][y][z]==0){ | |
puts("no route"); | |
exit(0); | |
} | |
puzzle[1][1][1]=0; | |
point tp; | |
tp.x=1; tp.y=1; tp.z=1; | |
tp.This=v.size(); tp.last=null; | |
v.PB(tp); | |
queue<point> q; | |
q.push(tp); | |
bool flag=false; | |
while(!q.empty()){ | |
point top=q.front(); | |
q.pop(); | |
if(top.x==x&&top.y==y&&top.z==z){ | |
tp=top; flag=true; break; | |
} | |
if(top.x-1>=1 && puzzle[top.x-1][top.y][top.z]){ | |
point n=top; | |
n.x-=1; | |
n.last=top.This; | |
n.This=v.size(); | |
q.push(n); | |
v.PB(n); | |
puzzle[top.x-1][top.y][top.z]=0; | |
} | |
if(top.x+1<=x && puzzle[top.x+1][top.y][top.z]){ | |
point n=top; | |
n.x+=1; | |
n.last=top.This; | |
n.This=v.size(); | |
q.push(n); | |
v.PB(n); | |
puzzle[top.x+1][top.y][top.z]=0; | |
} | |
if(top.y-1>=1 && puzzle[top.x][top.y-1][top.z]){ | |
point n=top; | |
n.y-=1; | |
n.last=top.This; | |
n.This=v.size(); | |
q.push(n); | |
v.PB(n); | |
puzzle[top.x][top.y-1][top.z]=0; | |
} | |
if(top.y+1<=y && puzzle[top.x][top.y+1][top.z]){ | |
point n=top; | |
n.y+=1; | |
n.last=top.This; | |
n.This=v.size(); | |
q.push(n); | |
v.PB(n); | |
puzzle[top.x][top.y+1][top.z]=0; | |
} | |
if(top.z-1>=1 && puzzle[top.x][top.y][top.z-1]){ | |
point n=top; | |
n.z-=1; | |
n.last=top.This; | |
n.This=v.size(); | |
q.push(n); | |
v.PB(n); | |
puzzle[top.x][top.y][top.z-1]=0; | |
} | |
if(top.z+1<=z && puzzle[top.x][top.y][top.z+1]){ | |
point n=top; | |
n.z+=1; | |
n.last=top.This; | |
n.This=v.size(); | |
q.push(n); | |
v.PB(n); | |
puzzle[top.x][top.y][top.z+1]=0; | |
} | |
} | |
if(!flag){ | |
puts("no route"); | |
}else{ | |
stack<point> ss; | |
int cur=tp.This; | |
while(cur!=null){ | |
ss.push(v[cur]); | |
cur = v[cur].last; | |
} | |
printf("(1,1,1)"); | |
ss.pop(); | |
for(;!ss.empty();ss.pop()){ | |
point ww=ss.top(); | |
printf("->(%d,%d,%d)",ww.x,ww.y,ww.z); | |
} | |
} | |
return 0; | |
} |
