답안 #22583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22583 2017-04-30T05:44:15 Z - - - - - - - List of honorable mention follows - - - - - - -(#999, xhae, ainu7, littlesheep) Young Zebra (KRIII5_YZ) C++14
0 / 7
500 ms 147856 KB
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int r, c;
vector<string> data;

vector<vector<int>> getCnt(vector<string> &field) {	
	int r = field.size(), c = field[0].size();
	vector<vector<int>> ret(r, vector<int>(c, -1));
	for(int i= 0; i < r; i++)
		for(int j= 0; j< c;j++) {
			if(ret[i][j] != -1) continue;
			ret[i][j] = 0;
			queue<tuple<int, int>> q;
			q.push(make_tuple(i, j));
			int cnt = 0;

			vector<tuple<int, int>> coords;
			while(!q.empty()) {
				cnt++;
				int y, x;
				tie(y, x) = q.front();
				coords.emplace_back(y, x);
				q.pop();

				const int mov[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
				for(int k = 0; k < 4; k++) {
					int ny = y + mov[k][0];
					int nx = x + mov[k][1];
					if(ny >= 0 and ny < r and nx >= 0 and nx < c and 
						ret[ny][nx] == -1 and field[ny][nx] == field[y][x]) {
						ret[ny][nx] = 0;
						q.push(make_tuple(ny, nx));
					}
				}
			}

			for(auto coord: coords) {
				int y, x;
				tie(y, x) = coord;
				ret[y][x] = cnt;
			}
		}
	return ret;
}

int main(void) {
	cin >> r >> c;
	data = vector<string>(r);
	for(int i =0 ; i <r; i++) cin >> data[i];

	vector<string> smallf(r * 3);
	vector<string> largef(r * 7);

	for(int i = 0; i < 3 * r; i++)
		for(int j = 0; j < 3; j++)
			smallf[i] += data[i % r];
	for(int i =0 ; i < 7 * r; i++)
		for(int j = 0; j < 7; j++)
			largef[i] += data[i % r];

	auto scnt = getCnt(smallf);
	auto lcnt = getCnt(largef);

	for(int i =0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			int v = -2;
			for(int q = 1; q <= 5; q++) {
				for(int w = 1; w <= 5; w++) {
					if(scnt[i + r][j + c] != lcnt[i + r * q][j + c * w]) {
						v = -1;
						break;
					} else {
						if(v == -2) v = scnt[i + r][j + c];
						else if(v != scnt[i + r][j + c]) {
							v = -1;
							break;
						}
					}
				}
				if(v == -1) break;
			}

			cout << v << " ";
		}
		cout << "\n";
	}

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 489 ms 57732 KB Output is correct
2 Execution timed out 500 ms 147856 KB Execution timed out
3 Halted 0 ms 0 KB -