[TIOJ] 1085. 三維迷宮問題
題目連結:http://tioj.infor.org/problems/1085
BFS題,記得紀錄一下路徑,然後要check一下起點可不可以走,不然會有一個subtaskWA,我的code那麼長基本上是六個方位一直複製貼上,然後就長爆了(?
BFS題,記得紀錄一下路徑,然後要check一下起點可不可以走,不然會有一個subtaskWA,我的code那麼長基本上是六個方位一直複製貼上,然後就長爆了(?
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define null 2147483647
bitset<55> puzzle[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();
while(!ss.empty()){
point ww=ss.top();
ss.pop();
printf("->(%d,%d,%d)",ww.x,ww.y,ww.z);
}
}
return 0;
}
留言
張貼留言