[swea 2112] 보호 필름

분류 : 구현

 

요구사항

셀을 d개 골라서 시험 조건 만족시키기

 

풀이

구현해야 할 것은 크게 3가지 있다.

1. 어느 셀을 선택할 것인지(dfs)

2. 선택한 셀을 바꿔주기

3. 조건에 부합하는지 검사하기

 

1번만 시간복잡도에 맞게 구현한다면 크게 어렵지 않은 문제이다

 

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;

int t;
int n, m, k;
int map[14][22];
int visit[22];
int ccnt = 0;
int ans = 987654321;
void change(int r, int num) {
	for (int i = 0; i < m; i++) {
		map[r][i] = num - 1;
	}
}
void solve(int cnt,int now)
{
	if (cnt >= ans) return;
	if (cnt > k) return;
	if (cnt <= k) {
		ccnt++;
		/*
		for (int i = 0; i < n; i++) {
			cout << visit[i] << " ";
		}
		cout << endl;
		*/
		int ansflag = 0;
		for (int i = 0; i < m; i++) {
			int num = 1;
			int flag = 0;
			for (int j = 0; j < n - 1; j++) {
				if (map[j][i] == map[j + 1][i]) {
					num++;
				}
				else {
					num = 1;
				}
				if (num == k) {
					flag = 1;
					break;
				}
			}
			if (flag == 1) continue;
			else {
				ansflag = 1;
				break;
			}
		}
		if (ansflag == 0)
		{
			//	cout << "!" << endl;
			ans = min(ans, cnt);
		}
	}
	if (cnt == k) return;
	for (int i = now; i < n; i++) {
		if (visit[i] == 0) {
			int mapc[14][22];
			memcpy(mapc, map, sizeof(map));
			visit[i] = 1;
			change(i, 1);
			solve(cnt + 1,i+1);
			visit[i] = 2;
			change(i, 2);
			solve(cnt + 1, i + 1);
			visit[i] = 0;
			memcpy(map, mapc, sizeof(map));
		}
	}
}
int main() {
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		ans = 987654321;
		memset(visit, 0, sizeof(visit));
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		solve(0,0);
		//cout << ccnt << endl;
		cout << "#" << tc << " " << ans << endl;
	}
}