글 읽기 - 반례가 더 있을까요..?

zhh1020 5년 전 0

질문에 있는 모든 반례는 적용해보았는데 맞았구.. 39%에서 틀립니다.
CCTV가 있는 위치와 형태를 vector에 삽입하고 백트래킹을 이용해서 각 카메라별 모든 조합을 구했습니다.
그 이후에 CCTV별 회전 케이스를 주어 맵에 9라는 값을 삽입해주었습니다.(6이면 break , 나머지 일 경우 9, CCTV가 있으면 continue)
그 이후에 맵의 0을 카운트했는데 잘 안나오네요..
반례가 궁금합니다
#include <iostream>
#include <vector>
using namespace std;
struct Info {
	int y, x;
	int dir;
};


struct Info TEMP;
const int MAX = 10;
vector<struct Info>vec[MAX*MAX];


int map[MAX][MAX];
int SET[MAX][MAX];
int n, m;
int ans;
int arr[MAX];

void RESET() {
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= m; x++) {
			map[y][x] = SET[y][x];
		}
	}
}

bool In(int y, int x) {
	return y >= 1 && y <= n && x >= 1 && x <= m;
}

void DRAW(int dir, int x, int y,int position) {

	switch (dir) {
	case 1:
		//cout << "one";
		switch (position) {
		case 0:
			if (In(y - 1, x)) {
				for (int dy = y - 1; dy >= 1; dy--) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			break;
		case 1:
			if (In(y, x + 1)) {
				for (int dx = x + 1; dx <= m; dx++) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}

			}
			break;
		case 2:
			if (In(y + 1, x)) {
				for (int dy = y + 1; dy <= n; dy++) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			break;
		case 3:
			if (In(y, x - 1)) {
				for (int dx = x - 1; dx >= 1; dx--) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			break;
		}
		break;
	case 2:
		//cout << "two"<<endl;
		switch (position) {
		case 0:
			if (In(y, x - 1)) {
				for (int dx = x - 1; dx >= 1; dx--) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			if (In(y, x + 1)) {
				for (int dx = x + 1; dx <= m; dx++) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}

			break;

		case 1:
			if (In(y - 1, x)) {
				for (int dy = y - 1; dy >= 1; dy--) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}

				if (In(y + 1, x)) {
					for (int dy = y + 1; dy <= n; dy++) {
						if (map[dy][x] == 6)
							break;
						else if (map[dy][x] == 0)
							map[dy][x] = 9;
						else
							continue;
					}
				}



				break;
			
			
		}
		break;
	case 3:
		//cout << "three";
		switch (position) {
		case 0:
			if (In(y - 1, x)) {
				for (int dy = y - 1; dy >= 1; dy--) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}

			if (In(y, x + 1)) {
				for (int dx = x + 1; dx <= m; dx++) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			break;
			
		case 1:
			if (In(y, x + 1)) {
				for (int dx = x + 1; dx <= m; dx++) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			if (In(y + 1, x)) {
				for (int dy = y + 1; dy <= n; dy++) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			break;
		case 2:
			//cout << "T";
			if (In(y, x - 1)) {
				for (int dx = x - 1; dx >= 1; dx--) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			//cout << "T1";
			//cout << y << " " << x;
			if (In(y + 1, x)) {
				//cout << "T2";
				for (int dy = y + 1; dy <= n; dy++) {
					//cout << dy << endl;
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			//cout << "W";
			break;
		case 3:
			if (In(y - 1, x)) {
				for (int dy = y - 1; dy >= 1; dy--) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			if (In(y, x - 1)) {
				for (int dx = x - 1; dx >= 1; dx--) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			break;
		}
		break;
	case 4:
		//cout << "four";
		switch (position) {
		case 0:
			if (In(y, x + 1)) {
				for (int dx = x + 1; dx <= m; dx++) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			if (In(y - 1, x)) {
				for (int dy = y + 1; dy <= n; dy++) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			if (In(y, x - 1)) {
				for (int dx = x - 1; dx >= 1; dx--) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			break;
		case 1:
			if (In(y - 1, x)) {
				for (int dy = y - 1; dy >= 1; dy--) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			if (In(y, x - 1)) {
				for (int dx = x - 1; dx >= 1; dx--) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			if (In(y + 1, x)) {
				for (int dy = y + 1; dy <= n; dy++) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			break;
		case 2:
			if (In(y - 1, x)) {
				for (int dy = y - 1; dy >= 1; dy--) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			if (In(y, x - 1)) {
				for (int dx = x - 1; dx >= 1; dx--) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			if (In(y, x + 1)) {
				for (int dx = x + 1; dx <= m; dx++) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			break;
		case 3:
			if (In(y, x + 1)) {
				for (int dx = x + 1; dx <= m; dx++) {
					if (map[y][dx] == 6)
						break;
					else if (map[y][dx] == 0)
						map[y][dx] = 9;
					else
						continue;
				}
			}
			if (In(y + 1, x)) {
				for (int dy = y + 1; dy <= n; dy++) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			if (In(y - 1, x)) {
				for (int dy = y - 1; dy >= 1; dy--) {
					if (map[dy][x] == 6)
						break;
					else if (map[dy][x] == 0)
						map[dy][x] = 9;
					else
						continue;
				}
			}
			break;
		}
		break;


	case 5:	//4방향을 그립니다.
		//cout << "five";
			//상
		if (In(y - 1, x)) {
			for (int dy = y - 1; dy >= 1; dy--) {
				if (map[dy][x] == 6)
					break;
				else if (map[dy][x] == 0)
					map[dy][x] = 9;
				else
					continue;
			}
		}
			//하
		if (In(y + 1, x)) {
			for (int dy = y + 1; dy <= n; dy++) {
				if (map[dy][x] == 6)
					break;
				else if (map[dy][x] == 0)
					map[dy][x] = 9;
				else
					continue;
			}
		}
			//좌
		if (In(y, x - 1)) {
			for (int dx = x - 1; dx >= 1; dx--) {
				if (map[y][dx] == 6)
					break;
				else if (map[y][dx] == 0)
					map[y][dx] = 9;
				else
					continue;
			}
		}
			//우
		if (In(y, x + 1)) {
			for (int dx = x + 1; dx <= m; dx++) {
				if (map[y][dx] == 6)
					break;
				else if (map[y][dx] == 0)
					map[y][dx] = 9;
				else
					continue;
			}
		}

		
		

	}
	//cout << "pass";
}


void back_traking(int depth, int SIZE) {
	if (depth >= SIZE) {
		int value = 0;
		//cout << endl;
		for (int i = 0; i < SIZE; i++) {
			int current_x = vec[i].front().x;
			int current_y = vec[i].front().y;
			int current_dir = vec[i].front().dir;
			//cout << arr[i] << " ";
			int position = arr[i];
			DRAW(current_dir, current_x, current_y, position);
		}

		//cout << endl;
		//cout << endl;
		
		for (int y = 1; y <= n; y++) {
			for (int x = 1; x <= m; x++) {
			//	cout << map[y][x] << " ";
				if (map[y][x] == 0)
					value++;
			}
			//cout << endl;
		}

		//cout << endl;
		//cout << value << endl;
		//if (value != 0) {
			if (value < ans)
				ans = value;
		//}

		RESET();
		return;
	}
	
	int CCTV = map[vec[depth].front().y][vec[depth].front().x];
	switch (CCTV) {
	case 2:
		for (int i = 0; i < 2; i++) {
			arr[depth] = i;
			back_traking(depth + 1, SIZE);
		}
		break;
	case 5:
		arr[depth] = 0;
		back_traking(depth + 1, SIZE);
		break;
	default: 
		for (int i = 0; i < 4; i++) {
			arr[depth] = i;
			back_traking(depth + 1, SIZE);
		}
		break;
	
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	ans = n * m;
	int cnt = 0;
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= m; x++) {
			cin >> map[y][x];
			SET[y][x] = map[y][x];
			if (map[y][x] >= 1 && map[y][x] <= 5) {		//CCTV 위치, 형태 삽입
				TEMP.x = x;
				TEMP.y = y;
				TEMP.dir = map[y][x];
				vec[cnt++].push_back(TEMP);
			}
		}
	}

	int SIZE = cnt;
	/*if (SIZE == 0) {
		cout << 0;
		return 0;
	}*/
	
	back_traking(0, SIZE);
	

	cout << ans;

}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례가 더 있을까요..?

zhh1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
