글 읽기 - 주먹구구식으로 case 나누어서 백트래킹 했다구 생각하는데

jerryprk 4년 전 0

감이안오네요 무엇이 잘못되었을지
각 케이스별로 시작할때 저장되온 배열 copy 후

copy array를 update 해가는방식으로 구현했습니다

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

#define MAX 9
int watch, h, w, low = MAX*MAX;
int mab[MAX][MAX];
bool visit[MAX][MAX];

int oY[4] = { 0,0,-1,1 };
int oX[4] = { -1,1,0,0 };
int tY[2] = { -1,1 };
int tX[2] = { -1,1 };
int TY[4] = { -1,-1,1,1 };
int TX[4] = { -1,1,-1,1 };
pair<int, pair<int, int> > cctv[MAX];
bool range(int y, int x) {
	if (y<0 || x<0 || y>h - 1 || x>w - 1)
		return false;
	else
		return true;
}
void copymap(int a[MAX][MAX], int b[MAX][MAX]) {
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			a[i][j] = b[i][j];
}
void view(int array[MAX][MAX]) {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++)
			printf("%2d ", array[i][j]);
		cout << endl;
	}
	cout << endl;
}
// cctv는 벽과, 맵밖을 갈 수 없으므로 배제
// cctv는 cctv를 통과할 수 있으므로 신경쓰지않음
void solve(int array[MAX][MAX], int cnt) {
    // 모든 cctv를 돌아봤을경우
    // 맵에 사각지대를 찾고, 최소치 저장후 종료
	if (cnt == watch) {
		int result = 0;
		for(int i=0;i<h;i++)
			for (int j = 0; j < w; j++) {
				if (array[i][j] == 0) result++;
			}
		low = min(low, result);
		return;
	}
	int type = cctv[cnt].first;
	int y = cctv[cnt].second.first;
	int x = cctv[cnt].second.second;

	int temp[MAX][MAX] = { 0, };
	int temp2[MAX][MAX] = { 0, };
	int ny = y, nx = x;
	switch (type) {
	case 1:
        // 상하좌우 한방향만 탐색가능한경우
		for (int i = 0; i < 4; i++) {
			copymap(temp, array);
			ny = y, nx = x;
			while (1) {
				ny += oY[i]; nx += oX[i];
				if (range(ny, nx) && temp[ny][nx] != 6) {
					temp[ny][nx] = '#';
				}
				else
					break;
			}
            // 각방향으로 맵update후 다음 cctv로
			solve(temp, cnt + 1);
		}
		break;
	case 2:
		// 좌우
		copymap(temp, array);
		for (int i = 0; i < 2; i++) {
			ny = y, nx = x;
			while (1) {
				nx += tX[i];
				if (range(ny, nx) && temp[ny][nx] != 6) {
					temp[ny][nx] = '#';
				}
				else
					break;
			}
		}
        // 좌우로 맵update후 다음 cctv로
		solve(temp, cnt + 1);
		// 상하
		copymap(temp, array);
		for (int i = 0; i < 2; i++) {
			ny = y, nx = x;
			while (1) {
				ny += tY[i];
				if (range(ny, nx) && temp[ny][nx] != 6) {
					temp[ny][nx] = '#';
				}
				else
					break;
			}
		}
        // 상하로 맵update후 다음 cctv로
		solve(temp, cnt + 1);
		break;
	case 3:
		for (int i = 0; i < 4; i++) {
			copymap(temp, array);
			ny = y, nx = x;
			while (1) {
				ny += TY[i];
				if (range(ny, nx) && temp[ny][nx] != 6) {
					temp[ny][nx] = '#';
				}
				else
					break;
			}
			while (1) {
				nx += TX[i];
				if (range(ny, nx) && temp[ny][nx] != 6) {
					temp[ny][nx] = '#';
				}
				else
					break;
			}
            // 총 4가지의 수직방향으로 진행후 맵update, nextcctv
			solve(temp, cnt + 1);
		}
		break;
	case 4:
		copymap(temp, array);
		for (int i = 0; i < 4; i++) {
			ny = y, nx = x;
			while (1) {
				ny += oY[i], nx += oX[i];
				if (range(ny, nx) && mab[ny][nx] != 6) {
					temp[ny][nx] = '#';
				}
				else
					break;
			}
		}
        // 맵에대해 4방향전부 view로 update후
        // 한방향에대해 blind update처리
		for (int i = 0; i < 4; i++) {
			copymap(temp2, temp);
			ny = y, nx = x;
			while (1) {
				ny += oY[i], nx += oX[i];
				if (range(ny, nx) && mab[ny][nx] != 6) {
					temp2[ny][nx] = 0;
				}
				else
					break;
			}
			solve(temp2, cnt + 1);
		}
		break;
	case 5:
        // 4방향에 대해 전부 view update후 nextcctv
		copymap(temp, array);
		for (int i = 0; i < 4; i++) {
			ny = y, nx = x;
			while (1) {
				ny += oY[i], nx += oX[i];
				if (range(ny, nx) && mab[ny][nx] != 6) {
					temp[ny][nx] = '#';
				}
				else
					break;
			}
		}
		solve(temp, cnt + 1);
		break;
	}
}
int main() {
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d %d", &h, &w);
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++) {
			scanf("%d", &mab[i][j]);
			if (mab[i][j]!=0 && mab[i][j] != 6) {
				cctv[watch++] = make_pair(mab[i][j], make_pair(i, j));
			}
		}
	solve(mab,0);
	printf("%d", low);
}

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

문제

문제

출처

ICPC

주먹구구식으로 case 나누어서 백트래킹 했다구 생각하는데

jerryprk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말