글 읽기 - 틀렸습니다가 떳는데 도저히 감을 못잡겠습니다 도와주세용 ㅜㅜ

fixi2 2년 전 0

도와주세요 고수님들 ㅠㅠㅠㅠ

반례가 있는걸까요,,?

#include <iostream>
#include <math.h>

using namespace std;

typedef struct Node {
	int x;
	int y;
	int use = 0;
}node;

node house[100];
node chicken[13];
int n, m;
int chicken_cnt, house_cnt;
int ans;

void dfs(int num, int cnt);

int main() {

	cin >> n >> m;
	ans = 50000;
	int x;
	house_cnt = 0;
	chicken_cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x;
			if (x == 1) {
				house[house_cnt].x = i;
				house[house_cnt].y = j;
				house_cnt++;
			}
			else if (x == 2) {
				chicken[chicken_cnt].x = i;
				chicken[chicken_cnt].y = j;
				chicken_cnt++;
			}
		}
	}

	dfs(0, 0);
	
	cout << ans;

	return 0;
}

void dfs(int num, int cnt) {
	if (num > chicken_cnt) {
		return;
	}

	if (cnt == m) {
		int mmax = 0;
		for (int i = 0; i < house_cnt; i++) {
			int temp = 50000;
			for (int j = 0; j < chicken_cnt; j++) {
				
				if (chicken[j].use == 1) {
					int temp2 = abs(house[i].x - chicken[j].x) + abs(house[i].y - chicken[j].y);
					if (temp > temp2) {
						temp = temp2;
					}
				}
			}
			mmax += temp;
		}

		if (ans > mmax) {
			ans = mmax;
		}

	}

	chicken[num].use = 1;
	dfs(num + 1, cnt + 1);
	chicken[num].use = 0;
	dfs(num + 1, cnt);
}

jh05013 2년 전 0

Random counterexample generator
8
0 0 2 1 0
2 2 0 1 0
0 1 0 0 0
2 0 2 2 0
0 1 0 1 2
2 2 0 2 0
Correct: 7
WRONG: 8

7
1 0 0 2 1
2 2 0 2 0
1 2 1 0 0
0 2 0 0 2
2 0 2 2 1
1 0 1 0 1
Correct: 9
WRONG: 19

10
2 1 2 1 0
1 0 0 1 1
0 2 1 0 1
0 2 2 1 0
0 0 2 1 0
0 1 2 2 1
Correct: 17
WRONG: 22

5
2 1 0 0 2
0 2 1 2 1
0 0 0 2 0
2 2 2 0 0
2 2 1 2 0
0 0 0 0 2
Correct: 6
WRONG: 10

Test completed in 11.944380044937134 seconds

fixi2 2년 전 0

위에 테케 다 정답이 나옵니다만.. ㅠㅠㅠ

jh05013 2년 전 0

https://ideone.com/Kukpti

제 컴퓨터와 다른 온라인 컴파일러에서는 위와 같이 나옵니다.

초기화되지 않은 변수나 배열, 또는 지정된 범위 밖의 배열 참조를 하면 무슨 일이 일어날 지 모릅니다.

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

문제

문제

출처

ICPC

틀렸습니다가 떳는데 도저히 감을 못잡겠습니다 도와주세용 ㅜㅜ

fixi2 2년 전 0

jh05013 2년 전 0

fixi2 2년 전 0

jh05013 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말