글 읽기 - 반례 또는 틀린이유를 알 수 있을까요?? 도움요청합니다.

parkwj93 5년 전 0

게시판에 반례는 모두 맞게 나오는데 어디가 틀린지 잘모르겠네요..
dfs로 풀었고 벡터에 cctv위치를 넣었고 이차원배열을 복사하고 넘기는 방식으로 풀었습니다.
그리고 공간의 개수의 경우 0의 개수를 세는 방식으로 구현했습니다.
반례 또는 틀린 부분 도움요청합니다.
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int n, m;
char map[9][9];
vector<pair<int,int>>v;
int result = 64;
int cnt = 0;
void printMap() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << map[i][j];
		}
		cout << "\n";
	}
}
int countSpace(char map2[][9]) {
	int a = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map2[i][j] == '0') {
				a++;
			}
		}
	}
	return a;
}
void copyMap(char(*map2)[9],char (*map3)[9]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			map3[i][j] = map2[i][j];
		}
	}
}
char (*dir(int a,int type,int row,int col, char (*map2)[9]))[9] {
	if (a == 1) {
		if (type == 0) {
		//위
			for (int i = row; i < n; i++) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
		}
		else if (type == 1) {
		//아래
			for (int i = row; i >= 0; i--) {
				if (map2[i][col] == '6') {
					break;
				}if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
		}
		else if (type == 2) {
		//오른
			for (int i = col; i < m; i++) {
				if (map2[row][i] == '6') {
					break;
				}if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
		}
		else if (type == 3) {
		//왼
			for (int i = col; i >= 0; i--) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
		}
	}
	else if (a == 2) {
		if (type == 0) {
		//좌우
			for (int i = col; i < m; i++) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
			for (int i = col; i >= 0; i--) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
		}
		else if (type == 1) {
		//위아래
			for (int i = row; i < n; i++) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
			for (int i = row; i >= 0; i--) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
		}
	}
	else if (a == 3) {
		if (type == 0) {
			//위오
			for (int i = row; i < n; i++) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
			for (int i = col; i < m; i++) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
		}
		else if (type == 1) {
			//오아래
			for (int i = col; i < m; i++) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
			for (int i = row; i >= 0; i--) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
		}
		else if (type == 2) {
			//아래왼
			for (int i = row; i >= 0; i--) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
			for (int i = col; i >= 0; i--) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
		}
		else if (type == 3) {
			//왼위
			for (int i = col; i >= 0; i--) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
			for (int i = row; i < n; i++) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
		}
	}
	else if (a == 4) {
		if (type == 0) {
			for (int i = col; i < m; i++) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
			for (int i = col; i >= 0; i--) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
			for (int i = row; i < n; i++) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
		}
		else if (type == 1) {
			for (int i = col; i < m; i++) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
			for (int i = col; i >= 0; i--) {
				if (map2[row][i] == '6') {
					break;
				}
				if (map2[row][i] == '0') {
					map2[row][i] = '#';
				}
			}
			for (int i = row; i >= 0; i--) {
				if (map2[i][col] == '6') {
					break;
				}
				if (map2[i][col] == '0') {
					map2[i][col] = '#';
				}
			}
		}
	}
	else if (a == 5) {
		for (int i = col; i < m; i++) {
			if (map2[row][i] == '6') {
				break;
			}
			if (map2[row][i] == '0') {
				map2[row][i] = '#';
			}
		}
		for (int i = col; i >= 0; i--) {
			if (map2[row][i] == '6') {
				break;
			}
			if (map2[row][i] == '0') {
				map2[row][i] = '#';
			}
		}
		for (int i = row; i < n; i++) {
			if (map2[i][col] == '6') {
				break;
			}
			if (map2[i][col] == '0') {
				map2[i][col] = '#';
			}
		}
		for (int i = row; i >= 0; i--) {
			if (map2[i][col] == '6') {
				break;
			}
			if (map2[i][col] == '0') {
				map2[i][col] = '#';
			}
		}
	}
	return map2;
}

void solve(int len,char (*map2)[9]) {
	if (cnt == len) {
		int result2 = countSpace(map2);
		if (result > result2) {
			result = result2;
		}
		return;
	}
	
		int y = v[len].first;
		int x = v[len].second;
		len = len + 1;
		if (map2[y][x] == '1') {
			for (int i = 0; i < 4; i++) {
				char map4[9][9];
				copyMap(map2,map4);
				char (*map3)[9]=dir(1, i,y,x,map2);
				solve(len, map3);
				copyMap(map4, map2);
			}
		}
		else if (map2[y][x] == '2') {
			for (int i = 0; i < 2; i++) {
				char map4[9][9];
				copyMap(map2, map4);
				char(*map3)[9]=dir(2, i,y,x,map2);
				solve(len, map3);
				copyMap(map4, map2);
			}
		}
		else if (map2[y][x] == '3') {
			for (int i = 0; i < 4; i++) {
				char map4[9][9];
				copyMap(map2, map4);
				char(*map3)[9]=dir(3, i,y,x,map2);
				solve(len, map3);
				copyMap(map4, map2);
			}
		}
		else if (map2[y][x] == '4') {
			for (int i = 0; i < 2; i++) {
				char map4[9][9];
				copyMap(map2, map4);
				char(*map3)[9]=dir(4, i,y,x,map2);
				solve(len, map3);
				copyMap(map4, map2);
			}
		}
		else if (map2[y][x] == '5') {
			char map4[9][9];
			copyMap(map2, map4);
			char(*map3)[9]=dir(5,0,y,x,map2);
			solve(len,map3);
			copyMap(map4, map2);
		}
	
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] != '0'&&map[i][j] != '6') {
				v.push_back(make_pair(i, j));
				cnt++;
			}
		}
	}
	solve(0,map);
	cout << result;
	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례 또는 틀린이유를 알 수 있을까요?? 도움요청합니다.

parkwj93 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
