//嚇人的鳥
#include?
#include?
using?namespace?std;

typedef?int32_t?int32;
typedef?uint32_t?uint32;

struct?Location?{
	int32?x;
	int32?y;
	Location（）?{?x=0?y=0;?}
	Location（int32?a?int32?b）?{?x=a?y=b;?}
};

void?Bresenham（int32?x1?int32?y1?int32?x2?int32?y2?vector&?locationVec）
{
????????bool?swapflag?=?false;
????????if?（x1?>?x2）{
????????????????int32?tmpx?=?x1;
????????????????int32?tmpy?=?y1;
????????????????x1?=?x2;
????????????????y1?=?y2;
????????????????x2?=?tmpx;
????????????????y2?=?tmpy;
????????????????swapflag?=?true;
????????}
????????
????????int32?dx?=?x2-x1;
????????int32?dy?=?y2-y1;
????????int32?x?=?x1;
????????int32?y?=?y1;
????????int32?sub?=?（dy<<1）-dx;
????????locationVec.push_back（Location（x?y））;
????????while（x????????????????++x;
????????????????if?（sub?>?0）{
????????????????????????sub?+=?（dy<<1）?-?（dx<<1）;
????????????????????????++y;
????????????????}else?{
????????????????????????sub?+=?（dy<<1）;
????????????????}
????????????????locationVec.push_back（Location（x?y））;
????????}

????????if?（swapflag）{
????????????????uint32?size?=?locationVec.size（）;
????????????????for?（uint32?i?=?0;?i?????????????????????????Location?tmp?=?locationVec[i];
????????????????????????locationVec[i]?=?locationVec[size-i-1];
????????????????????????locationVec[size-i-1]?=?tmp;
????????????????}
????????}
}

void?CalcShortestDistance（const?Location&?startPos?const?Location&?endPos?vector&?locationVec）
{
	if?（startPos.x==endPos.x?&&?startPos.y==endPos.y）
		return?;
	
	if?（endPos.x?==?startPos.x）{?//x相同
		if?（endPos.y?>?startPos.y）{
			for?（uint32?i?=?0;?i?				loca