POJ2308连连看dfs+bfs+优化

时间:2022-09-07 08:09:20

DFS+BFS+MAP+剪枝

题意:

      就是给你一个10*10的连连看状态,然后问你最后能不能全部消没?

思路:

     首先要明确这是一个搜索题目,还有就是关键的一点就是连连看这个游戏是存在决策的,就是如果当前的这个点可以连接好几个点的话,我们选择那个点连接是不一样的,所以还要遍历所有的可能连接点,这样考虑的话单纯的一个搜索肯定不行了,可以用一个深搜套广搜的的结构,深搜是为了遍历顺序,广搜所为了得到当前点可以消去那些点(必要一个一个搜,要直接把所有的可能都搜出来,就是把杭电的那个bfs扩展下),但是直接暴力时间复杂度肯定接受不了,目测是,目测是多少我也不知道,但是存在这样的数据t = O(100^25),所以要优化,关键是在优化,下面是我能想到的几个优化

(1)首先把所有的卡片都单独拿出来,放到一个结构体里面,这样每次遍历的时候直接就只遍历数组,不用遍历所有的图。

(2)直接判断每种卡片出现的次数的奇偶。

(3)还有就是开一个状态记录当前的这个状态是否出现过,这个我是用的map进行hash的,这个优化有种记忆化搜索的感觉。

(4)还有最后一个(百度的),也是最关键的,如果有两种卡片都只剩下两个了,并且出现这样的姿势

AB

BA

   显然这样是连接不了的,这样感觉不会优化多少,但是在这个题目里,这样貌似优化很大,原因我感觉是在卡片的种类上的原因,卡片种类只有4种,这个也只是猜测,其实我力推的优化是(2,3)可惜没有4一直超时。

还有就是一定要明确,连连看是存在决策问题的。

#include<map>

#include<queue>

#include<stdio.h>

#include<string.h>

#include<string>

using namespace std;

typedef struct

{

    int x ,y ,t;

}NODE;

typedef struct

{

    int x ,y;

}CARD;

NODE xin ,tou;

CARD card[105];

CARD can[105];

int ss[5];

int cans ,mkans ,n ,m ,nowc ,cards;

int _map[12][12];

int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};

map<string ,int>MARK;

bool ok(int x ,int y)

{

    return x >= 1 && x <= n && y >= 1 && y <= m && (!_map[x][y] || _map[x][y] == nowc);

}

bool jude()

{

    char str[105];

    for(int i = 1 ;i <= cards ;i ++)

    if(_map[card[i].x][card[i].y]) str[i-1] = 'a';

    else str[i-1] = 'b';

    str[cards] = '\0';

    if(MARK[str]) return 0;

    MARK[str] = 1;

    return 1;

}

int BFS(int x ,int y)

{

    int mark[12][12] = {0};

    nowc = _map[x][y];

    cans = 0;

    xin.x = x ,xin.y = y ,xin.t = 0;

    queue<NODE>q;

    q.push(xin);

    while(!q.empty())

    {

        tou = q.front();

        q.pop();

        if(_map[tou.x][tou.y] == nowc && !(tou.x == x && tou.y == y))

        {

            cans ++;

            can[cans].x = tou.x;

            can[cans].y = tou.y;

            continue;

        }

        if(tou.t >= 3) continue;

        for(int i = 0 ;i < 4 ;i ++)

        {

            xin.x = tou.x ,xin.y = tou.y ,xin.t = tou.t + 1;

            while(1)

            {

                xin.x += dir[i][0];

                xin.y += dir[i][1];

                if(!ok(xin.x ,xin.y)) break;

                if(!mark[xin.x][xin.y])

                {

                    mark[xin.x][xin.y] = 1;

                    q.push(xin);

                }

            }

        }

    }

    return cans;

}

bool CCC(int a ,int b)

{

    for(int i = 1 ;i <= cards ;i ++)

    {

        int x = card[i].x ,y = card[i].y;

        if(_map[x][y] == a)

        {

            if(_map[x+1][y+1] == a && _map[x+1][y] == b && _map[x][y+1] == b)

            return 1;

            return 0;

        }

        if(_map[x][y] == b)

        {

            if(_map[x+1][y+1] == b && _map[x+1][y] == a && _map[x][y+1] == a)

            return 1;

            return 0;

        }

    }

}

bool CUT()

{

    for(int i = 1 ;i <= 4 ;i ++)

    for(int j = i + 1 ;j <= 4 ;j ++)

    {

        if(ss[i] == ss[j] && ss[i] == 2)

        {

            if(CCC(i ,j)) return 1;

        }

    }

    return 0;

}

void DFS(int nows)

{

    if(!nows) mkans = 1;

    if(mkans) return ;

    if(!jude()) return ;

    if(CUT()) return ;

    for(int i = 1 ;i <= cards ;i ++)

    {

        if(mkans) return ;

        int x = card[i].x ,y = card[i].y;

        if(!_map[x][y]) continue;

        BFS(x ,y);

        ss[_map[x][y]] -= 2;

        for(int j = 1 ;j <= cans ;j ++)

        {

            int tmp = _map[x][y];

            int xx = can[j].x ,yy = can[j].y;

            _map[x][y] = _map[xx][yy] = 0;

            DFS(nows - 2);

            _map[x][y] = _map[xx][yy] = tmp;

        }

        ss[_map[x][y]] += 2;

    }

}

int main ()

{

    char str[12];

    while(~scanf("%d %d" ,&n ,&m) && n + m)

    {

        memset(_map ,0 ,sizeof(_map));

        memset(ss ,0 ,sizeof(ss));

        cards = 0;

        for(int i = 1 ;i <= n ;i ++)

        {

            scanf("%s" ,str);

            for(int j = 1 ;j <= m ;j ++)

            {

                if(str[j-1] == '*') _map[i][j] = 0;

                else

                {

                    _map[i][j] = str[j-1] - 'A' + 1;

                    cards ++;

                    card[cards].x = i;

                    card[cards].y = j;

                    ss[_map[i][j]] ++;

                }

            }

        }

        if(ss[1]%2 || ss[2]%2 || ss[3]%2 || ss[4]%2)

        {

            printf("no\n");

            continue;

        }

        mkans = 0;

        MARK.clear();

        DFS(cards);

        mkans ? printf("yes\n"):printf("no\n");

    }

    return 0;

}

POJ2308连连看dfs+bfs+优化的更多相关文章

  1. DFS&sol;BFS&plus;思维 HDOJ 5325 Crazy Bobo

    题目传送门 /* 题意:给一个树,节点上有权值,问最多能找出多少个点满足在树上是连通的并且按照权值排序后相邻的点 在树上的路径权值都小于这两个点 DFS/BFS+思维:按照权值的大小,从小的到大的连有 ...

  2. 【DFS&sol;BFS】NYOJ-58-最少步数(迷宫最短路径问题)

    [题目链接:NYOJ-58] 经典的搜索问题,想必这题用广搜的会比较多,所以我首先使的也是广搜,但其实深搜同样也是可以的. 不考虑剪枝的话,两种方法实践消耗相同,但是深搜相比广搜内存低一点. 我想,因 ...

  3. ID(dfs&plus;bfs&rpar;-hdu-4127-Flood-it&excl;

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4127 题目意思: 给n*n的方格,每个格子有一种颜色(0~5),每次可以选择一种颜色,使得和左上角相 ...

  4. hdu 4109 dfs&plus;剪枝优化

    求最久时间即在无环有向图里求最远路径 dfs+剪枝优化 从0节点(自己添加的)出发,0到1~n个节点之间的距离为1.mt[i]表示从0点到第i个节点眼下所得的最长路径 #include<iost ...

  5. &lbrack;LeetCode&rsqb; 130&period; Surrounded Regions&lowbar;Medium tag&colon; DFS&sol;BFS

    Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A reg ...

  6. HDU 4771 &lpar;DFS&plus;BFS&rpar;

    Problem Description Harry Potter has some precious. For example, his invisible robe, his wand and hi ...

  7. DFS&sol;BFS视频讲解

    视频链接:https://www.bilibili.com/video/av12019553?share_medium=android&share_source=qq&bbid=XZ7 ...

  8. 2013年第四届蓝桥杯国赛 九宫重排(HashMap&plus;双BFS优化)

    九宫重排     时间限制:1.0s   内存限制:256.0MB 问题描述 如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着.与空格子相邻的格子中的卡片可以移动到空格中.经过若干 ...

  9. POJ 3083 -- Children of the Candy Corn(DFS&plus;BFS)TLE

    POJ 3083 -- Children of the Candy Corn(DFS+BFS) 题意: 给定一个迷宫,S是起点,E是终点,#是墙不可走,.可以走 1)先输出左转优先时,从S到E的步数 ...

随机推荐

  1. eclipse构建maven&plus;scala&plus;spark工程 转载

    转载地址:http://jingpin.jikexueyuan.com/article/47043.html 本文先叙述如何配置eclipse中maven+scala的开发环境,之后,叙述如何实现sp ...

  2. c中的指针

    一. 指针前奏 1. 指针的重要性 指针是C语言中非常重要的数据类型,如果你说C语言中除了指针,其他你都学得很好,那你干脆说没学过C语言. 2. 小需求 l void change(int  n)函数 ...

  3. ServletContext中常用方法(getRsource和getResourceAsStream)

    转自:http://blog.csdn.net/yakson/article/details/9203267 一..获取Tomcat的Context的初始化参数. 1.获取Tomcat的server. ...

  4. div样式调整小结 转载

    1.多个div使用会自动换行,应该使用float属性  left : 对象浮在左边  right : 对象浮在右边 例如:  float: left  和 float: right 是两个div左右排 ...

  5. 超级易使用的jquery视频背景插件Vide

    http://www.jqcool.net/demo/201410/jquery-vide/ 官网: http://vodkabears.github.io/vide/

  6. C语言的本质(31)——C语言与汇编之函数调用的本质

    我们一段代码来研究函数调用的过程.首先我们写一段简单的小程序: int sum(int c, int d) { inte = c + d; returne; } int func(int a, int ...

  7. Apple Swift 中文教程 高速參考 基本的语法

    总的来说.语法有java的味道,也有python的味道,还有swift自己的味道. 有些语法还是挺不伦不类的,不太好理解,即使你有几年的java或python经验,也不见得有些语法你能非常轻松的看明确 ...

  8. django&period;core&period;exceptions&period;ImproperlyConfigured&colon; mysqlclient 1&period;3&period;13 or newer is required&semi; you have 0&period;9&period;3&period;

    异常汇总:https://www.cnblogs.com/dotnetcrazy/p/9192089.html 这个是Django对MySQLdb版本的限制,我们使用的是PyMySQL,所以不用管它 ...

  9. better-scroll 中的img标签无法触发长按保存菜单

    better-scroll 默认禁用的多数标签的默认行为,启用默认行为需加如下属性 preventDefaultException: { tagName: /^(IMG|INPUT|TEXTAREA| ...

  10. IOS 颜色的宏定义

    #define RGB(r, g, b, a) [UIColor colorWithRed:r/255.0 green:g/255.0 blue:b/255.0 alpha:a]   self.vie ...