解題思路：可以一行一行地遞歸求解，要是不符合條件就回溯，注意最后一行不能夠移動(dòng)它，因?yàn)榭赡軙?huì)與之前重疊。。

#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\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 2078(搜索+剪枝)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。