poj2078(검색+가지치기)

1017 단어 검색

문제 풀이 사고방식: 한 줄 한 줄 반복해서 해답을 구할 수 있고 조건에 부합되지 않으면 거슬러 올라가서 마지막 줄이 이전과 중첩될 수 있으므로 주의해야 한다.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 8;
int n,mat[maxn][maxn],ans;

int get_max(int dep)
{
	int m = 0, sum = 0;
	for(int i = 1; i <= n; i++){
		sum = 0;
		for(int j = 1; j <= dep; j++){
			sum += mat[j][i];
		}
		m = max(m,sum);
	}
	return m;
}

void dfs(int dep)
{
	int tmp,m;
	if(dep == n){
		m = get_max(dep);
		if(m < ans) ans = m;
		return;
	}
	for(int i = 1; i <= n; i++){
		tmp = mat[dep][1];
		for(int j = 2; j <= n; j++){
			swap(tmp,mat[dep][j]);
		}
		swap(tmp,mat[dep][1]);
		m = get_max(dep);
		if(m > ans) continue;
		dfs(dep+1);
	}
}

int main()
{
	while(scanf("%d",&n),n != -1){
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				scanf("%d",&mat[i][j]);
		ans = get_max(n);
		dfs(1);
		printf("%d
",ans); } return 0; }

좋은 웹페이지 즐겨찾기