이차원 배열과 연산 (feat. 백준, 17140번)

이차원 배열과 연산
https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/17140
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
short R, C, K;
short r_length, c_length;
short maps[101][101];
short set[101];
vector<pair<short, short>> tmp;
int length;
inline const bool cmp(const pair<int, int>& v1, const pair<int, int>& v2) {
	if (v1.second == v2.second) return v1.first < v2.first;
	return v1.second < v2.second;
}

inline void r_calc() {
	length = 0;
	for (int ix = 1, iy, tmp_size; ix <= r_length; ++ix) {
		for (iy = 1; iy <= c_length; ++iy) {
			if (maps[ix][iy] != 0)
				++set[maps[ix][iy]];
			maps[ix][iy] = 0;
		}
		tmp_size = 0;
		tmp.clear();
		for (iy = 1; iy <= 100; ++iy)
			if (set[iy] != 0)
				tmp.push_back(make_pair(iy, set[iy])), set[iy] = 0, ++tmp_size;
		sort(tmp.begin(), tmp.end(), cmp);
		if (tmp_size > 50)		tmp_size = 50;
		length = max(length, tmp_size * 2);
		for (iy = 1; iy <= tmp_size; ++iy)
			maps[ix][iy * 2 - 1] = tmp[iy - 1].first, maps[ix][iy * 2] = tmp[iy - 1].second;
	}
	c_length = length;
}
void c_calc() {
	length = 0;
	for (int iy = 1, ix, tmp_size; iy <= c_length; ++iy) {
		for (ix = 1; ix <= r_length; ++ix) {
			if (maps[ix][iy] != 0)
				++set[maps[ix][iy]];
			maps[ix][iy] = 0;
		}
		tmp_size = 0;
		tmp.clear();
		for (ix = 1; ix <= 100; ++ix)
			if (set[ix] != 0)
				tmp.push_back(make_pair(ix, set[ix])), set[ix] = 0, ++tmp_size;
		sort(tmp.begin(), tmp.end(), cmp);
		if (tmp_size > 50)		tmp_size = 50;
		length = max(length, tmp_size * 2);
		for (ix = 1; ix <= tmp_size; ++ix)
			maps[ix * 2 - 1][iy] = tmp[ix - 1].first, maps[ix * 2][iy] = tmp[ix - 1].second;
	}
	r_length = length;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	for (int ix = 1, iy; ix <= 100; ++ix) {
		set[ix] = 0;
		for (iy = 1; iy <= 100; ++iy)
			maps[ix][iy] = 0;
	}
	r_length = c_length = 3;
	cin >> R >> C >> K;
	for (int ix = 1, iy; ix <= 3; ++ix)
		for (iy = 1; iy <= 3; ++iy)
			cin >> maps[ix][iy];
	
	auto result = 0;
	for (result = 0; result <= 100; ++result)
	{
		if (maps[R][C] == K)		break;
		if (r_length >= c_length)	r_calc();
		else						c_calc();
	}
	if (result > 100)
		cout << -1 << endl;
	else
		cout << result << endl;
	return 0;
}
// *&)*@*

1. stl map도 사용해 보았으나, 배열과 메모리 차이는 없었습니다.