POJ2965 状态压缩+BFS,DFS枚举,以及大牛的解法~

POJ2965 状态压缩+BFS,DFS枚举,以及大牛的解法~

和poj1753非常相似,这题用状态压缩+BFS同样可以解,状态压缩就是用二进制来表示一种状态。

这是我在1753上改的BFS+状态压缩代码:

 

//二进制+BFS写法
#include<iostream>
using namespace std;   //解决问题路径搜索

bool flag[65536];
int step[65536];
struct con
{
    int f;
    int k;
}connect[65536];
int ans[65536];
int qstate[65536];  //搜索状态
int top=0;
int rear=0;
void Init()
{
    int temp=0;
    char c;
    for(int i=0; i < 4; i++)
         for(int j = 0; j < 4; j++)
         {
             cin>>c;
             if('+' == c)
                 temp |= (1<<(i*4+j));
         }
    qstate[rear++] = temp;
     flag[temp]  = true;
}

int move(int state,int i)
{
    int temp=0;
    temp |= (1<<i);     //翻自己
    int j;
    for(j=i;(j+1)%4!=0;j++)//右
    temp |= (1<<(j+1));
    for(j=i;(j)%4!=0;j--)//左
    temp |= (1<<(j-1));
    for(j=i;(j-4)>=0;j=j-4)//上
    temp |= (1<<(j-4));
    for(j=i;(j+4)<16;j=j+4)//下
    temp |= (1<<(j+4));

    return (state ^ temp);
}

bool BFS()
 {
     while(rear > top)
     {
         int state = qstate[top++];
         for(int i=0; i < 16; i++)
         {
             int temp;
             temp = move(state,i);
             if(0 == state)
             {
                 cout<<step[state]<<endl;
                 int x=0;
                 for(int j=step[state]-1;j>=0;j--)
                 {
                     ans[j]=connect[x].k;
                     x=connect[x].f;
                 }
                 for(int j=0;j<step[state];j++)
                 {
                     cout<<(ans[j]/4)+1<<' '<<(ans[j]%4)+1<<endl;
                 }
                 return true;
             }
             else if(!flag[temp]) //防止重复搜索
             {
                 qstate[rear++] = temp;
                 flag[temp] = true;
                 step[temp] = step[state]+1;
                 connect[temp].f=state;
                 connect[temp].k=i;
             }
         }
     }

     return false;
 }
 int main(void)
 {
     Init();
     BFS();
     return 0;
 }

然后是参考网上DFS枚举的方法,以后将继续对DFS枚举进行理解。代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10;
struct node
{
    int p, q;
}a[18];
int map[N][N], ans, flag;
void Change(int x, int y) //翻转函数
{
    int i;
    map[x][y] = !map[x][y];
    for (i = 1; i <= 4; ++i)
    {
        map[x][i] = !map[x][i];
        map[i][y] = !map[i][y];
    }
}
int Judge() //判断函数
{
    int i, j;
    for (i = 1; i <= 4; ++i)
    {
        for (j = 1; j <= 4; ++j)
        {
            if (map[i][j] == 0)
            {
                return 0;
            }
        }
    }
    return 1;
}
void DFS(int x, int y, int step)
{
    if (step == ans)
    {
        flag = Judge();//不能加if(flag),否则超时
        return ;
    }
    if (flag || x >= 5)
    {
        return ;
    }
    Change(x, y);
    if (y < 4)
    {
        DFS(x, y + 1, step + 1);
        a[step].p = x;
        a[step].q = y;
    }
    else                                //全部16枚举一遍
    {
        DFS(x + 1, 1, step + 1);
        a[step].p = x;
        a[step].q = y;
    }
    Change(x, y);                       //再原路返还
    if (y < 4)
    {
        DFS(x, y + 1, step);
    }
    else
    {
        DFS(x + 1, 1, step);
    }
}
int main()
{
    int i, j;
    char str;
    for (i = 1; i <= 4; ++i)
    {
        for (j = 1; j <= 4; ++j)
        {
            scanf("%c", &str);
            if (str == '-')
            {
                map[i][j] = 1;
            }
            else
            {
                map[i][j] = 0;
            }
        }
        getchar();//度掉回车
    }
    flag = 0;
    for (i = 0; i <= 16; ++i)
    {
        ans = i;
        DFS(1, 1, 0);
        if (flag)
        {
            break;
        }
    }
    if (flag)
    {
        printf("%d\n", ans);
        for (i = 0; i < ans; ++i)
        {
            printf("%d %d\n", a[i].p, a[i].q);
        }
    }
    return 0;
}

 

 

 

再最后就是网上大神的算法,找到其中巧妙的规律。这也提醒我以后多将过程展示出来可从中发现重要的信息!:

/*既然说要把所有的开关变成是打开的话,那么怎么样才能做而且又不影响其他的布局呢?如果没遇到一个‘+’即关闭的开关,我们就把这个开关所在行和列包括它本身(本身只操作一次)都操作一次的话。那么可以计算它本身的状态变化次数为7,其同在一行和一列的元素则状态变化为4,余下的状态转化都是2.可以得到这个方法可以在不影响其它元素的状态下将关闭的开关打开(因为偶数次对状态实际上是没有影响的)。所有我们只要遇到一个'+'就重复上面的操作,而且用一个数组记录下每个元素被操作的次数。最后扫描一次数组,操作次数为奇数的就是我们需要操作的点(偶数次操作相当于没有操作)。
代码:*/
#include<stdio.h>
long m[5][5] ;
void dose(int x,int y){//没操作一次就对元素标记数组加一
for(int i = 1;i<=4;i++){
m[x][i]++ ;
if(i!=x)m[i][y]++ ;
}
}
int steps(){//计算需要操作的次数
int c = 0 ;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
if(m[i][j]%2) c++ ;
return c ;
}
int main()
{
int
char c ;
for(i = 1 ; i <= 4 ; i++){
for(j = 1 ; j <= 4 ; j++){
scanf("%c",&c) ;
if(c=='+') dose(i,j) ;
}
getchar() ;
}
printf("%d\n",steps()) ;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
if(m[i][j]%2)//遇到是奇数的就打印出来
printf("%d %d\n",i,j) ;
return 0 ;
}

 

当然还有一种纯纯的暴力枚举也能过。。用16个for语句的枚举。。

 

转载于:https://www.cnblogs.com/amourjun/archive/2013/03/15/5134220.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110191.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • servlet和jsp的区别与联系。

    servlet和jsp的区别与联系。什么是servlet:(1)Servlet是一种服务器端的Java应用程序,具有独立于平台和协议的特性,可以生成动态的Web页面。(2)它担当客户请求(Web浏览器或其他HTTP客户程序)与服务器响应(HTTP服务器上的数据库或应用程序)的中间层。什么是jsp:(1)JSP全名为JavaServerPages,中文名叫java服务器页面,其根本是一个简化的Servlet设计,它[1

  • c++ pushback函数_push back from

    c++ pushback函数_push back from算法中里面的一个函数名,如c++中的vector头文件里面就有这个push_back函数,在vector类中作用为在vector尾部加入一个数据。string中也有这个函数,作用是字符串之后插入一个字符。如果是指标准模板库(stl)中容器的一般pushback()操作函数,那么是指在容器尾端插入一项数据,比如vectora(10);a.pushback(10);那么a的尾端,同时也是唯…

    2022年10月24日
  • C# OpenFileDialog SaveFileDialog Filter

    C# OpenFileDialog SaveFileDialog Filter那个Filter的格式每次都要忘,很讨厌,记录之: OpenFileDialogofd=newOpenFileDialog();ofd.Filter=”pc信息文件(*.vcf)|*.vcf|所有文件(*.*)|*.*”;if(ofd.ShowDialog()!=System.Windows.Forms.Di

  • js正則表達式语法

    js正則表達式语法

    2021年12月10日
  • 基准测试框架JMH使用详解

    基准测试框架JMH使用详解JMH简介JMH即JavaMicrobenchmarkHarness,是Java用来做基准测试的一个工具,该工具由OpenJDK提供并维护,测试结果可信度高。基准测试Benchmark是测量、评估软件性能指标的一种测试,对某个特定目标场景的某项性能指标进行定量的和可对比的测试。项目中添加依赖创建一个基准测试项目,在项目中引入JMH的jar包,目前JMH的最新版本为1.23。以maven为例,依赖配置如下。<dependencies><dependency

  • IdeaVim中文输入体验优化

    IdeaVim中文输入体验优化IntelljIDEA是一个非常不错的JavaIDE,IdeaVim插件更是让喜欢用vim的我兴奋不已。但是IdeaVim对中文输入的支持不太好,要频繁切换中英文很麻烦。今年推荐一款插件可能解决这个问题哦。目前只支持Windows和mac。效果如下:安装插件输入法的小插件IdeaVimExtension你都用上IdeaVim了,说明我就不用介绍IDEA如何安装插件了,有问题请留言。配置在~/.ideavimrc中增加如下两行。:setkeep-english-in-normal:s

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号