yukicoder : No.1588 Connection

実装問？
https://yukicoder.me/problems/no/1588

問題

N*Nのグリッドがあり、うちMマスだけ黒く塗られていて残しは白マスである。
左上マスから、右下マスまで、隣接する黒マスをたどって移動可能か判定したい。

なお、初期状態でマスの色は与えられない。
マスを指定し、その色を知るクエリを、最大3M回実行可能であるものとする。

解法

BFSかDFSで、移動可能なマスの隣接マスに対し、移動可能かたどっていこう。
新たなマスに移動したとき、移動前のマスは、移動可能であることがわかっているので、その隣接マスは高々3回までしかクエリを実行する必要がない。よって最大クエリ回数は3M回以下である。

int N,M;

int C[1010][1010];

void dfs(int y,int x) {
	if(y<0||y>=N||x<0||x>=N) return;
	if(C[y][x]>=0) return;
	cout<<(1+y)<<" "<<(1+x)<<endl;
	string s;
	cin>>s;
	C[y][x]=(s=="Black");
	
	if(C[y][x]) {
		dfs(y-1,x);
		dfs(y,x-1);
		dfs(y+1,x);
		dfs(y,x+1);
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(C);
	
	cin>>N>>M;
	dfs(0,0);
	
	if(C[N-1][N-1]==1) {
		cout<<"Yes"<<endl;
	}
	else {
		cout<<"No"<<endl;
	}
}

まとめ

★2.5位でもいい気がする。