【POJ – 2078】Matrix（dfs）

–>Matrix

Descriptions:

输入一个n×n的矩阵，可以对矩阵的每行进行任意次的循环右移操作，行的每一次右移后，计算矩阵中每一列的和的最大值，输出这些最大值中的最小值。

Sample Input

2
4 6
3 7
3
1 2 3
4 5 6
7 8 9
-1

Sample Output

11
15

题目链接

https://vjudge.net/problem/POJ-2078

 

使用dfs解决，对于n×n的矩阵来说，行循环右移后，矩阵最多有n^n中可能的状态，在这题中最多有7^7=823543中状态，是可以暴力搜索的。使用dfs搜索这些状态，并计算矩阵每个状态的列和的最大值，输出最大值中的最小值即可。

 

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 30
using namespace std;
int n;
int mp[Maxn][Maxn];
int ans;
void init(int x) //对行mp[x][]循环右移一次
{
    int t=mp[x][n-1];
    for(int j=n-1; j>0; j--)
        mp[x][j]=mp[x][j-1];
    mp[x][0]=t;
}
void dfs(int x)
{
    if(x==n)
    {
        int maxSum=-INF; //列和的最大值
        for(int i=0; i<n; i++)
        {
            int sum=0;
            for(int j=0; j<n; j++)
                sum+=mp[j][i];
            maxSum=max(sum,maxSum);
        }
        ans=min(maxSum,ans);//保存列和最大值中的最小值
    }
    else
    {
        for(int i=0; i<n; i++) //每一行都循环右移n次
        {
            init(x);
            dfs(x+1);
        }
    }
}
int main()
{

    while(cin>>n,n!=-1)
    {
        MEM(mp,0);
        ans=INF; 
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>mp[i][j];
        dfs(0);//开始搜索
        cout<<ans<<endl;
    }
    return 0;
}

 

posted on 2019-07-18 21:18 Sky丨Star 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为sky-stars原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/sky-stars/p/11210053.html