Submission #205140

---

Source Code Expand

#include "maze.h"
#include "grader.h"
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; ++i)
const int dx[] = {-1,0,1,0,0};
const int dy[] = {0,-1,0,1,0};

int dir[1000][1000];
void dfs(int i, int j, int v, int M[1000][1000]) {
	dir[i][j] = v;
	rep(u,4) {
		if (v == u || M[i+dx[u]][j+dy[u]]) continue;
		dfs(i+dx[u]*2,j+dy[u]*2,u^2,M);
	}
}

int sch(int v, int u, int ma){
	int l = 0, r = ma, c;
	while (l+1<r) {
		c = l+r>>1;
		if (query(dy[v]*c*2+dy[u],dx[v]*c*2+dx[u])) r = c; else l = c;
	}
	return l;
}
void get(int& x, int& y, int W, int H) {
	int lx, ly, rx, ry;
	int dv = 4;
	lx = sch(0,dv,H/2);
	rx = sch(2,dv,H/2);
	if (lx+rx != H/2-1) {
		rep(v,4){
			if (query(dy[v],dx[v]) == 0) {
				dv = v;
				break;
			}
		}
		lx = sch(0,dv,H/2);
		rx = sch(2,dv,H/2);
	}
	ly = sch(1,dv,W/2);
	ry = sch(3,dv,W/2);
	if (ly+ry != W/2-1) {
		rep(v,4){
			if (query(dy[v],dx[v]) == 0) {
				dv = v;
				break;
			}
		}
		ly = sch(1,dv,W/2);
		ry = sch(3,dv,W/2);
	}
	x = lx*2+1-dx[dv];
	y = ly*2+1-dy[dv];
}

void taro(int W, int H, int M[1000][1000]) {
	dfs(1,1,100,M);
	for(int i = 1; i <= H-2; i += 2) {
		for(int j = 1; j <= W-2; j += 2) {
			if (i == 1 && j == 1) continue;
			send(dir[i][j]>>1);
			send(dir[i][j]&1);
		}
	}
	int x, y;
	get(x,y,W,H);
	rep(i,9){ send(x&1); x>>=1;}
	rep(i,9){ send(y&1); y>>=1;}
}

int m[1000][1000];
int dist(int i, int j, int v, int x, int y, int M[1000][1000]){
	if (i == x && j == y) return 0;
	rep(u,4) {
		if (v == u || M[i+dx[u]][j+dy[u]]) continue;
		int res = dist(i+dx[u],j+dy[u],u^2,x,y,M);
		if (res != -1) return res+1;
	}
	return -1;
}
int jiro(int W, int H, int S, int X[]) {
	int cur = 0;
	rep(i,H)rep(j,W) m[i][j] = ((i%2&&j%2)?0:1);
	for(int i = 1; i <= H-2; i += 2) {
		for(int j = 1; j <= W-2; j += 2) {
			if (i == 1 && j == 1) continue;
			int v = X[cur++]<<1 | X[cur++];
			m[i+dx[v]][j+dy[v]] = 0;
		}
	}
	int sx = 0, sy = 0;
	cur = S;
	rep(i,9) sy = sy<<1 | X[--cur];
	rep(i,9) sx = sx<<1 | X[--cur];
	int x, y;
	get(x,y,W,H);
	return dist(sx, sy, -1, x, y, m);
}

Submission Info

Judge Result