首页 > 其他 > 详细

poj 2965

时间:2014-05-26 02:19:49      阅读:438      评论:0      收藏:0      [点我收藏+]

题意 : 4*4的+,-组成  每次能翻转一个点所在的行与列 求最小的翻转次数 使得矩阵全为-

思路:暴力枚举

bubuko.com,布布扣
#include<iostream>
using namespace std;
int map[5][5];
int b;
int n;
int rsult[22];
void slip(int i,int s[][4])//翻转
{
    int k;
    int x=i/4;
    int y=i%4;
    s[x][y]=!s[x][y];
    for(k=0;k<4;k++)
    {
        s[x][k]=!s[x][k];
        s[k][y]=!s[k][y];
    }
}
bool all(int s[][4])//判断是否全为-号
{
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(s[i][j]==0)
                return false;
    return true;
}
void output()//输出翻转次序
{
    cout<<n<<endl;
    for(int i=0;i<n;i++)
        cout<<rsult[i]/4+1<<" "<<rsult[i]%4+1<<endl;
}
void judge()//每搜索到一个肯能解就判断一下
{
    int i,j;
    int now[4][4];
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
        now[i][j]=map[i][j];
    for(i=0;i<n;i++)
        slip(rsult[i],now);
    if(all(now))
    {
        b=1;
        output();
    }
}
void dfs(int start,int count)//最先搜索到的解肯定是最优解
{
    if(b) return ;
    if(count<=0)
    {
        judge();
        return ;
    }
    for(int i=start;i<=16-count;i++)
    {
        rsult[n-count]=i;
        dfs(i+1,count-1);
    }
}
int main()
{
    int i,j;
    char str[5];
    int x,y;
    x=y=0;
    for(i=0;i<4;i++)
    {
        cin>>str;
        for(j=0;j<4;j++)
        {
            if(str[j]==+)
            {
                x++;
                map[i][j]=0;
            }
            else 
            {
                y++;
                map[i][j]=1;
            }
        }
    }
    b=0;
    if(y==16)
        cout<<0<<endl;
    else
    for(i=1;i<=16;i++)
    {
        n=i;
        if(b) break;
        dfs(0,i);
    }
    return 0;
}
bubuko.com,布布扣

 

poj 2965,布布扣,bubuko.com

poj 2965

原文:http://www.cnblogs.com/zhangdashuai/p/3749456.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!