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)


相关推荐

  • Charles抓包指南

    Charles抓包指南1.进入Charles官网下载。2.安装Charles后,进行注册。help—>register—>input—>ok!RegisteredName:https://zhile.ioLicenseKey:48891cf209c6d32bf43.运行Charles,并进行配置。手机设置代理后,浏览器访问:chls.pro/ssl会下载证书,然后进入手机设置-安全设置-导入证书即可。小米手机需要第三方浏览器打开链接进行下载,否则下载的.

  • HashMap底层实现原理_hadoop原理

    HashMap底层实现原理_hadoop原理Note:文章的内容基于JDK1.7进行分析,1.8做的改动文章末尾进行讲解。大家可以看一下:https://www.imooc.com/article/267756一、先来熟悉一下我们常用的HashMap1、概述HashMap基于Map接口实现,元素以键值对的方式存储,并且允许使用null建和null 值, 因为key不允许重复,因此只能有一个键为null,另外HashMap不…

  • java实现数据库同步的方法_java数据库同步中间层使用

    java实现数据库同步的方法_java数据库同步中间层使用之前也有用过数据库的同步中间件比如阿里的canal,最近突发奇想,自己使用Java进行不同数据库品牌的数据库同步,比如Oracle同步到MySQL,等等;正文…

    2022年10月15日
  • java专业是什么专业,写的太详细了「建议收藏」

    java专业是什么专业,写的太详细了「建议收藏」前言SQL语句执行慢的原因是面试中经常会被问到的,对于服务端开发来说也是必须要关注的问题。在生产环境中,SQL执行慢是很严重的事件。那么如何定位慢SQL、慢的原因及如何防患于未然。接下来带着这些问题让我们开启本期之旅!第1章:Dubbo的简史、后续的规划和整体架构大图————Dubbo高性能RPC通信框架1.1应用架构演进过程1.2Dubbo简介1.3Dubbo总体大图第2章:Dubbo的环境配置和基于Dubbo开发第一款应用程序————开发第一款Dubbo应用程序

  • phpstorm2021免费版 激活码破解方法

    phpstorm2021免费版 激活码破解方法,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • python字符串内置方法[通俗易懂]

    字符串的内置方法(部分)

发表回复

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

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