Submission #25356

---

Source Code Expand

#include<queue>
#include<cstdio>
#include<algorithm>
#include"maze.h"
#include"grader.h"

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct point{
	int x,y;
	point(){}
	point(int x,int y):x(x),y(y){}
};

void taro(int W,int H,int M[1000][1000]){
	int tx=INF,ty=INF;
	for(int y=-1000;y<=1000;y++) for(int x=-1000;x<=1000;x++) {
		if(query(x,y)==0){
			tx=min(tx,x);
			ty=min(ty,y);
		}
	}
	tx=1-tx; ty=1-ty;

	rep(y,H) rep(x,W) if(x%2^y%2) send(M[y][x]);
	rep(i,10) send(!!(tx&1<<i));
	rep(i,10) send(!!(ty&1<<i));
}

int jiro(int W,int H,int n_sig,int sig[]){
	int i_sig=0;
	static int M[1000][1000];
	rep(y,H) rep(x,W) {
		if(x%2^y%2) M[y][x]=sig[i_sig++];
		else        M[y][x]=(x%2&&y%2?0:1);
	}

	int tx=0,ty=0; // taro のいる座標
	rep(i,10) tx|=sig[i_sig++]<<i;
	rep(i,10) ty|=sig[i_sig++]<<i;

	int jx=INF,jy=INF;
	for(int y=-1000;y<=1000;y++) for(int x=-1000;x<=1000;x++) {
		if(query(x,y)==0){
			jx=min(jx,x);
			jy=min(jy,y);
		}
	}
	jx=1-jx; jy=1-jy;

	// BFS
	static int d[1000][1000];
	rep(y,H) rep(x,W) d[y][x]=INF;
	d[jy][jx]=0;

	queue<point> Q;
	Q.push(point(jx,jy));
	while(!Q.empty()){
		int x=Q.front().x,y=Q.front().y; Q.pop();
		rep(k,4){
			int xx=x+dx[k],yy=y+dy[k];
			if(M[yy][xx]==0 && d[yy][xx]==INF){
				d[yy][xx]=d[y][x]+1;
				Q.push(point(xx,yy));
			}
		}
	}

	return d[ty][tx];
}

Submission Info

Judge Result