今日のATCとかなんとか

チャレンジしてました。三問中一問AC。

まずはこれ。
A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder
深さ優先探索は最近やったしいけるかなと思ったけどわりと時間がかかった。
でもリファレンスを見ないで解けたぞ。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int h, w;
int machi[500][500] = {0};
int issearched[500][500] = {0};
int tesu[500][500] = {0};

int tansaku(int sx, int sy, int gx, int gy);

int main()
{
	cin >> h >> w;
	char c;
	int sx, sy, gx, gy;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> c;
			if(c == 's'){
				sx = i;
				sy = j;
			} else if(c == 'g'){
				gx = i;
				gy = j;
				machi[i][j] = 1;
			} else if(c == '.') machi[i][j] = 1;
			else if(c == '#') machi[i][j] = 0;
		}
	}
	int ans = tansaku(sx, sy, gx, gy);
	if(ans == 0) cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}

int tansaku(int sx, int sy, int gx, int gy)
{
	queue<pair<int, int> > qu;
	int nx, ny;
	qu.push(pair<int, int> (sx, sy));
	while(!qu.empty()){
		int x = qu.front().first;
		int y = qu.front().second;
		for(int i = 0; i < 4; i++){
			nx = x + dx[i];
			ny = y + dy[i];
			if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
			else{
				if(machi[nx][ny] == 1 && issearched[nx][ny] == 0){
					issearched[nx][ny] = 1;
					tesu[nx][ny] = tesu[x][y] + 1;
					if(nx == gx && ny == gy) break;
					else qu.push(pair<int, int> (nx, ny));
				}
			}
		}
		qu.pop();
	}
	return tesu[gx][gy];
}

深さ優先探索ではキューを使うんですね。
幅優先探索でもそうなんですけれど、dxとdyの使い方を初めて知った時は感動しました。
ゴールの時がうまく書けなかった。別にmachi[gx][gy]に1を入れなくてもうまくやる方法あるんじゃないのかな。

ここまでで40分。うーんもうちょっと早く書けそうなのに。
で、二問目に取り掛かります。
B: Union Find - AtCoder Typical Contest 001 | AtCoder

で、コード。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>

using namespace std;

void renketsu(int a, int b);
bool hantei(int a, int b, string s);

int n, q, p, a, b;
int ischained[100001][100001] = {0};

int main()
{
	cin >> n >> q;
	for(int i = 0; i <= n; i++){
		ischained[i][i] = 1;
	}
	for(int i = 0; i < q; i++){
		cin >> p >> a >> b;
		if(p == 0) renketsu(a, b);
		else if(p == 1){
			if(hantei(a, b, "!")) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	return 0;
}

void renketsu(int a, int b)
{
	ischained[a][b] = 1;
	ischained[b][a] = 1;
	return;
}

bool hantei(int a, int b, string s)
{
	for(int i = 0; i <= n; i++){
		if(ischained[a][i] == 1){
			if(i == b) return true;
			else{
				int tmp = 0;
				for(int j = 0; j < s.length(); j++){
					if(s[j] == i + '0') tmp = 1;
					break;
				}
				if(tmp) continue;
				else {
					s += i + '0';
					return hantei(i, b, s);
				}
			}
		}
	}
	return false;
}

点aと点bが繋がっているか否かの情報を保存するのにischainedを用いた。繋がっている場合は1、そうでない場合は0が入っている。
同じ点同士は繋がっているとするからmainのなかの2~4行目でischained[i][i]に1を代入。
その後、pの値に合わせて連結したり判断したりします。
renketsuは見たまま。
handanについて。文字列sは今まで通ってきた点の情報が入っているはず(最初に「！」を入れたのはなんとなく。今思えばaでも入れておけばよかったかも…)。まず0から順に点aと繋がっているところを見ていく。見つかったところが点bであればtureを返す。それ以外はsの中に数字iがあるか探す。ある場合はダメなので次にうつるようにcontinue。ない場合はsに数字iを加えて今度はiからbへとべるように探していく…というふうにしたつもり。

ターミナルでコンパイル、実行したところsample inputがうまくいったのでいそいで提出…が、

よくわからないコンパイルエラーが出た。C+11でもダメ。
そのまま時間になったので終了。

うーん、でもこれ間違ってる気がする。returnがうまくいってなさそう。
また明日にでも考えよう。