[TIOJ] 1085. 三維迷宮問題

題目連結:http://tioj.infor.org/problems/1085

---

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;
}