[TIOJ] 1143. 4.靈犬尋寶

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

---

本題顯然是個BFS題，然後記得如果一個點在queue裡面了，那其他比他晚進入的同一個點必定$times \geq 原本的$，所以不妨直接把他設成不能走，免得重複走同一個點。
p.s 這是我第一次寫這種C++的struct跟class，有點醜，抱歉。

#include <bits/stdc++.h>
using namespace std;

#define N 100

bitset<N+5> block[N+5];

struct pos{
	int x,y,times;
	pos(){};
	pos(int t){times=t;}
	pos(int a, int b){
		x=a;
		y=b;
	}
	bool operator==(const pos& a){
		return a.x==x&&a.y==y;
	}
	pos top(){return pos(x,y-1);}
	pos down(){return pos(x,y+1);}
	pos left(){return pos(x-1,y);}
	pos right(){return pos(x+1,y);}
};

inline bool isBlock(const pos &a){
	if(a.x<=N-1&&a.x>=0&&a.y<=N-1&&a.y>=0)
		return block[a.x][a.y];
	return 1;
}

class Q
{
	public:
		Q(){};
		Q(const pos &a){push(a);}
		inline void push(const pos& a){
			if(!isBlock(a)){
				qq.push(a);
				block[a.x][a.y]=1;
			}
		}
		inline bool empty(){return qq.empty();}
		inline pos top(){
			pos tp = qq.front();
			qq.pop();
			return tp;
		}
	private:
		queue<pos> qq;
};

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		block[x][y]=1;
	}
	bool flag=1;
	pos ss(0),ee;
	scanf("%d%d%d%d",&ss.x,&ss.y,&ee.x,&ee.y);
	Q qq(ss);
	while(!qq.empty()){
		pos inQ = qq.top();
		if(inQ==ee){
			printf("%d\n",inQ.times);
			flag=0;
			break;
		}
		pos test = inQ;
		test.times=inQ.times+1;
		if(!isBlock(inQ.top())){
			test.x=inQ.x+1;
			test.y=inQ.y-3;
			qq.push(test);
			test.x=inQ.x-1;
			qq.push(test);
		}
		if(!isBlock(inQ.down())){
			test.x=inQ.x+1;
			test.y=inQ.y+3;
			qq.push(test);
			test.x=inQ.x-1;
			qq.push(test);
		}
		if(!isBlock(inQ.left())){
			test.x=inQ.x-3;
			test.y=inQ.y+1;
			qq.push(test);
			test.y=inQ.y-1;
			qq.push(test);
		}
		if(!isBlock(inQ.right())){
			test.x=inQ.x+3;
			test.y=inQ.y+1;
			qq.push(test);
			test.y=inQ.y-1;
			qq.push(test);
		}
	}
	if(flag) puts("impossible");
	return 0;
}