文档章节

POJ -- 2965 The Pilots Brothers' refrigerator

傅芃芃
 傅芃芃
发布于 2016/03/19 21:14
字数 889
阅读 27
收藏 1

题目链接: POJ -- 2965

题目给出的是4X4的矩阵,规模不算大。由于问的是最少的操作步数,很容易想到bfs宽搜。一共16个格子,总共的状态数是2^16,不算大,所以这个策略的确是对的。

但是需要注意到每个“状态”都是一个4x4的矩阵,我们需要想办法去记录一个矩阵的状态。用整数是一个直观的方法,我们每次对当前矩阵做过变形后,新的矩阵存储于另一个二维数组中,然后再算出代表新矩阵状态的整数。我 们存储这个整数就好。

但是这么做是会超时的。原因是这个宽搜的出度特别大,出度也是16(当前矩阵每改变一个元素都会生成一个新矩阵,一共16个元素)。加上我们在矩阵和代表矩阵的整数之间做变换也需要消耗O(16)的时间,一共花掉了O(16^2)。一共2^16个状态,我们对每个状态做O(16^2)的操作,这个复杂度是大于10^7了,会超时。

解决的办法是利用位运算。我们将当前的矩阵用一个整数代表(和之前做的一样),当对元素(i, j)作翻转的时候,直接在整数上做文章就能完成(这个是可以达到的,就是很麻烦),这样不用在矩阵和整数之间来回转,省下了O(16)的复杂度。

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
typedef unsigned short ushort;
char g[10][10];
int vis[100000], path[100000], from[100000];
ushort q[100000];
int front, end;
ushort get_id(char g[10][10])
{
    ushort id = 0;
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            id <<= 1;
            if(g[i][j] == '+') id |= 1;
        }
    }
    return id;
}

ushort black_mask_r[4] = { (((1 << 4) - 1) << (3*4)), (((1 << 4) - 1) << (2*4)), (((1 << 4) - 1) << (1*4)), ((1 << 4) - 1) };
ushort white_mask_r[4] = { ~(((1 << 4) - 1) << (3*4)), ~(((1 << 4) - 1) << (2*4)), ~(((1 << 4) - 1) << (1*4)), ~((1 << 4) - 1) };
ushort mark = (1 | (1 << 4) | (1 << 2*4) | (1 << 3*4));
ushort black_mask_c[4] = { (mark << 3), (mark << 2), (mark << 1), mark};
ushort white_mask_c[4] = { ~(mark << 3), ~(mark << 2), ~(mark << 1), ~mark};

ushort change_ij(ushort st, int i, int j)
{
    ushort r = (st & black_mask_r[i]);
    r = ~r;
    r &= black_mask_r[i];
    ushort restr = st & white_mask_r[i];
    r = restr | r;

    ushort k = ((1 << (3-j)) << (4*(3-i)));
    r ^= k;

    ushort c = r & black_mask_c[j];
    c = ~c;
    c &= black_mask_c[j];
    ushort restc = r & white_mask_c[j];
    c = restc | c;
    return c;
}

ushort id;
void print_path(ushort st, int l)
{
    if(from[st] < 0)
    {
        printf("%d\n", l);
        return ;
    }
    print_path(q[from[st]], l+1);
    printf("%d %d\n", path[st]/4+1, path[st]%4+1);
}

int main()
{
    // freopen("in.txt", "r", stdin);

    for(int i = 0; i < 4; i++)
    {
        scanf("%s", g[i]);
    }
    id = get_id(g);

    vis[id] = 1; q[end++] = id; from[id] = -1;
    ushort ans = -1;
    while(front != end)
    {
        int index = front;
        ushort x = q[front++];
        if(!x) { ans = x; break; }
        for(int i = 0; i < 4; i++)
        {
            for(int j = 0; j < 4; j++)
            {
                ushort st = change_ij(x, i, j);
                if(!vis[st])
                {
                    q[end++] = st;
                    vis[st] = 1;
                    path[st] = 4*i+j;
                    from[st] = index;
                }
            }
        }
    }

    if(!ans)
    {
        print_path(0, 0);
    }
    return 0;
}

位运算的代码确实有点恶心,我编程能力差,调试了特别久。

代码优化时间就是用change_ij函数去代替在矩阵数组和整数之间来回转换,那个函数内部用的都是位运算,速度比4*4的循环快多了。

© 著作权归作者所有

傅芃芃
粉丝 14
博文 21
码字总数 19341
作品 0
私信 提问
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
156
1
jitsi缺少架包,该怎么引入

Auto-properties install: reference:file:sc-bundles/jitsi-lgpl-dependencies.jar (org.osgi.framework.BundleException: Unable to cache bundle: reference:file:sc-bundles/jitsi-lgpl-......

121045258
2015/12/16
518
1
python http 组件简介

mechanize https://pypi.python.org/pypi/mechanize/ 中文简介:基于urllib2,完全兼容urllib2,提供浏览历史,表单状态,cookies等功能。 mechanize 0.2.5 Downloads ↓ Stateful programma...

蔡清华
2013/06/06
263
0
POJ3723 《挑战程序设计竞赛》踩坑

我看书上的代码,觉得这一行有错误, 所以我就没这样写,我写的是 在codeblocks运行的好好的,来了poj一直报错,debug两个多小时,终于发现,书里的题目和poj上的题目,x,y表示的正好相反啊...

小太阳花儿
2017/12/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

for循环

九九乘法表 示例:for(int i = 1; i <= 9; i++){ for (int j = 1; j <= i; j++) { // 每次开始i循环,j都会重新定义为j=1,然后开始循环计算 System.out.print(j +......

Shutting
6分钟前
2
0
小王子1

一定要帅! 韩国设计师品牌 insgram全世界得网红 韩国潮男穿搭 HM 找到穿衣服最好看的人,跟他比,比他好看。 在兴趣前,不要表现目的性,压力 关系是不热就冷的! 不喜欢压力,不喜欢负责任...

阿锋zxf
25分钟前
5
0
时间戳

1 loadTimeString(ts) { var d = new Date(); if (String(ts).length == 10) { d = new Date(ts * 1000); ......

东方巨人
26分钟前
3
0
Redis Cluster

Redis Cluster 集群 redis集群有以下几种方式 普通一主多从 普通一主多从+哨兵 cluster分片模式 一主多从 搭建方式网上很多,就不多描述了。 这种集群方式,一般master用作写,slave用做读,...

lazy~
27分钟前
4
0
 介绍一款优秀的通用管理权限快速开发框架

这是一套以权限管理为主的轻量化快速开发框架,配置有流程、专业表单、权限、app、企业微信等基础功能模块,在开发通用软件的效率上很有优势。 软件平台常用研发需求分析 《那些年我们一起做...

我想造火箭
43分钟前
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部