10026号赤い薬水

2855 ワード
コーディングテスト テキストリンク
最近はsk hyonixの原書と英語でcoteができなかったので少しやらなくても、感覚が失われます.がんばってください!
この問題はかなり簡単だ.すくい取るには領域を区別する必要があるのでqueueを使用し、brootforceで囲み、個々に位置決めする必要があります.
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <string.h>
using namespace std;
char map[100][100];
int ch[100][100];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
struct Loc {
	int x, y;
	Loc(int a, int b) {
		x = a;
		y = b;
	}
};
int main() {
	int n;
	//freopen("in1.txt", "rt", stdin);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> map[i];
	}
	queue<Loc> Q;
	int cnt1 = 0;
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < n; y++) {
			if (ch[x][y] == 0) {
				Q.push(Loc(x, y));
				cnt1++;
				while (!Q.empty()) {
					Loc tmp = Q.front();
					Q.pop();
					for (int i = 0; i < 4; i++) {
						int xx = tmp.x + dx[i];
						int yy = tmp.y + dy[i];
						if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
						if (ch[xx][yy] == 0 && map[xx][yy] == map[tmp.x][tmp.y]) {
							ch[xx][yy] = 1;
							Q.push(Loc(xx, yy));
						}
					}
				}
			}
		}
	}
	memset(ch, 0, sizeof(ch));
	int cnt2 = 0;
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < n; y++) {
			if (ch[x][y] == 0) {
				Q.push(Loc(x, y));
				cnt2++;
				while (!Q.empty()) {
					Loc tmp = Q.front();
					Q.pop();
					for (int i = 0; i < 4; i++) {
						int xx = tmp.x + dx[i];
						int yy = tmp.y + dy[i];
						if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
						if (ch[xx][yy] == 0) {
							if ((map[tmp.x][tmp.y] == 'R' && map[xx][yy] == 'G') || (map[tmp.x][tmp.y] == 'G' && map[xx][yy] == 'R') || map[xx][yy] == map[tmp.x][tmp.y]) {
								ch[xx][yy] = 1;
								Q.push(Loc(xx, yy));
							}
						}
					}
				}
			}
		}
	}
	cout << cnt1 << " " << cnt2 << '\n';
	return 0;
}
HTML Tables
リモコンのイベント取得その2 タッチサーフェスの端のタッチを検知する