yukicoder : No.1315 渦巻洞穴

意外に手間取った。
https://yukicoder.me/problems/no/1315

問題

グリッド上で、渦巻き状に自然数が順に配置されている。
2つの自然数S,Tが指定されるので、SのあるセルからTのあるセルに隣接マスをたどりながら移動したい。
その際、通ったセルに配置された値のxorが0となる経路を答えよ。

なお、同じセルを複数回通ってもよく、その際はセルの値が毎回xorに計上される。

解法

SとTのマンハッタン距離が奇数の場合、通るマスの数は偶数個になる。
同じマスを行ったり来たりして、同じマスを2回ずつ通るようにすれば当然xorは0になる。

マンハッタン距離が偶数の場合、どこかで奇数個のマスを通ってxorが0となるような経路を含めばよい。
以下では、1→2→3または２→1→8→9→2を通るようにしている。

int S,T;

pair<int,int> pos(int v) {
	int i;
	for(i=1;;i+=2) {
		int cur=i*i;
		int nex=(i+2)*(i+2);
		int x,y;
		if(cur==v) return {i/2,-i/2};
		if(v<nex) {
			y=-i/2;
			x=i/2+1;
			v-=cur+1;
			int step=i+1;
			if(v<=step-1) return{x,y+v};
			y+=step-1;
			v-=step-1;
			if(v<=step) return{x-v,y};
			x-=step;
			v-=step;
			if(v<=step) return{x,y-v};
			y-=step;
			v-=step;
			return {x+v,y};
		}
	}
}

string R;

void go(int sx,int sy,int tx,int ty) {
	while(sx!=tx||sy!=ty) {
		if(sx<tx) sx++, R+="RLR";
		else if(sx>tx) sx--, R+="LRL";
		else if(sy<ty) sy++, R+="UDU";
		else if(sy>ty) sy--, R+="DUD";
		if(sx==tx&&sy==ty) break;
		
		if(sx<tx) sx++, R+="R";
		else if(sx>tx) sx--, R+="L";
		else if(sy<ty) sy++, R+="U";
		else if(sy>ty) sy--, R+="D";
		
		
	}
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	auto p=pos(S);
	auto q=pos(T);
	//cout<<p.first<<p.second<<endl;
	//cout<<q.first<<q.second<<endl;
	if(abs(p.first+p.second)%2==abs(q.first+q.second)%2) {
		if(abs(p.first+p.second)%2==0) {
			go(p.first,p.second,0,0);
			R+="RUL";
			p={0,1};
		}
		else {
			go(p.first,p.second,1,0);
			R+="DLURL";
			p={0,0};
		}
		//cout<<"#"+R<<endl;
	}
	//cout<<p.first<<p.second<<endl;
	go(p.first,p.second,q.first,q.second);
	cout<<0<<endl;
	cout<<R.size()<<endl;
	cout<<R<<endl;
}

まとめ

数値からセルを求める処理が一番めんどい？