SRM 243 DIV1 Hard TwoKings

問題 Editorial

問題

略

解答

Editorial参照。
最大でも4回でいけるので、全探索できる

コメント

この問題はおもいっきりそれっぽい感じで。書けないといけないな…
今もその4回のやり方わかってないけど

コード

#include <string>
#include <sstream>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define INF 0x3f3f3f3f
using namespace std;

struct TwoKings {
	void parse(string s, int& x, int& y) {
		stringstream ss(s);
		ss >> x >> y;
	}
	int qx, qy, kx[2], ky[2];
	bool canMove(int x1, int y1, int x2, int y2) {
		return x1 == x2 || y1 == y2 || x1 - y1 == x2 - y2 || 100 - x1 - y1 == 100 - x2 - y2;
	}
	int searchAll(bool side, int moves) {
		if(side == false) {
			int r = 4;
			if(moves == 3) {
				if(canMove(qx, qy, kx[0], ky[0]) || canMove(qx, qy, kx[1], ky[1])) return 3;
				else return 4;
			}
			rer(dx, -1, 1) rer(dy, -1, 1) if(dx || dy) rer(dd, 1, 100) {
				int xx = qx + dx * dd, yy = qy + dy * dd;
				if((kx[0] == xx && ky[0] == yy) || (kx[1] == xx && ky[1] == yy)) {
					return moves;
				}
				if(!(0 <= xx && xx < 100 && 0 <= yy && yy < 100)) continue;
				swap(qx, xx), swap(qy, yy);
				r = min(r, searchAll(true, moves+1));
				swap(qx, xx), swap(qy, yy);
			}
			return r;
		}else {
			int r = -INF;
			rep(kk, 2) rer(dx, -1, 1) rer(dy, -1, 1) if(dx || dy) {
				int xx = kx[kk] + dx, yy = ky[kk] + dy;
				if(!(0 <= xx && xx < 100 && 0 <= yy && yy < 100)) continue;
				if(xx == qx && yy == qy) continue;
				swap(kx[kk], xx), swap(ky[kk], yy);
				r = max(r, searchAll(false, moves));
				swap(kx[kk], xx), swap(ky[kk], yy);
				if(r == 4) return r;
			}
			return r;
		}
	}
	int captureKing(string queen, string king1, string king2) {
		parse(queen, qx, qy);
		parse(king1, kx[0], ky[0]);
		parse(king2, kx[1], ky[1]);
		return searchAll(false, 1);
	}
};