글 읽기 - 테스트케이스는 다 맞게나오는데 그냥 채점누르면 바로 틀렸습니다가 뜹니다....

rlagksrlf12 5년 전 0

조합을 썼는데 무엇이문제인지 잘모르겠어서 올려봅니다.....

#include<stdio.h>
#include<math.h>
int chi[14][2];
int ji[28][2];
int map[51][51];
int gu(int a, int b, int c, int d)
{
	return abs(a - b) + abs(c - d);
}
int bitcount(int n)
{
	int count = 0;
	while (n > 0)
	{
		if ((n & 1) == 1) count++;
		n = n >> 1;
	}
	return count;
}
int son(int n, int m, int l)
{
	int tmp, result = 987654321;
	for (int i = 0; i < (1 << n); i++)
	{
		int res = 987654321;
		int sum = 987654321;
		if (bitcount(i) == m)
		{
			sum = 0;
			for (int k = 0; k < l; k++)
			{
				int ret = 987654321;
				for (int j = 0; j < n; j++)
				{
					if (i&(1 << j))
					{
						tmp = gu(ji[k][0], chi[j][0], ji[k][1], chi[j][1]);
						if (tmp < ret)
						{
							ret = tmp;
						}
					}
				}
				sum += ret;
			}
		}
		if (sum< result) result = sum;
	}
	if (m == 0 || l == 0 || n == 0) return 0;
	return result;
}
int main()
{
	int n, m, k = 0, l = 0;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1)
			{
				ji[k][0] = i;
				ji[k][1] = j;
				k++;
			}
			if (map[i][j] == 2)
			{
				chi[l][0] = i;
				chi[l][1] = j;
				l++;
			}
		}
	}
	printf("%d", son(l, m, k));
	return 0;
}