$Mayan$游戏

时间：2023-01-23 20:05:54

\(Mayan\)游戏

好啊，一年（半年）来的梦魇，终于结束了。

其实我从来没料到整体竟然会如此暴力……做的时候机房里冷得很，感觉晕晕乎乎地做完了，晕晕乎乎地调了好久，晕晕乎乎地听(看了题解的)\(qcr\)给我讲怎么优化代码量，怎么剪枝。

  • 每次搜索要保留本次的状态，这是比较好想的，我也成功的想到了。但是问题是我们不能单纯地用一个二维数组来\(copy\)，需要记录步数，不然就会错误\(copy\_back\)。于是最终我们需要一个三维数组来记录。后半段是\(qcr\)告诉我的。

  • 大概就是……我从来没想到\(Mayan\)游戏，会让你每一层\(dfs\)真正地搜全部\(5 \times 7=35\)个块。

  • 还有就是一个小小的剪枝儿。就是由于对于每一个格子，我们考虑它向两边替换，而我们为了避免重复搜索，所以就决定单向搜索，即对于每个块，如果他左边也是一个块，那就不去\(exchange\)，只考虑右边；而如果左边是空白格，才\(exchange\)。显然这个剪枝儿的优化性是很显著的。

  • 我一开始写的\(remove()\)、\(down()\)和\(check()\)十分的麻烦——或者说专一?反正之后我懒得调试了，直接听的\(qcr\)的，每次执行这几个函数的时候，直接全屏扫一遍。

  • \(qcr\)给我讲了一个很神的\(down()\)函数。

  • 对于\(exchange\)，我们要不断的\(while(remove()) ~;\)，因为会不断地有新情况出现。

  • 最后我挂了……几个点来着……忘记了。反正原因是因为，每次\(remove()\)之前应该先\(down()\)，然而我并没有\(down()\)干净233

  • 最后再说一个剪枝儿，不是必要性的，但是确实可以加快速度。就是我们再每次遍历\(7 \times 5\)的时候，遇到空白的，不是continue而是break，因为我们\(down\)一定是完备的，所以可以少好几次空遍历。

  • 这是个好题，怎么说呢，折射我代码能力弱的好题。

  • 代码大概\(5k+\)左右

  • 向我自己致敬

// luogu-judger-enable-o2

#include <stack>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std ;

struct D{ int x, y ;} ; stack <D> s ;

struct Ans{ int x, y, d  ;} res[100] ; int Remove[50][50] ;

int N, T[30][30], base[4000][10][10], qwq[4000][30], color[30], i, j, t, tot ;

inline int qr(){

    int res = 0 ; char c = getchar() ;

    while (!isdigit(c)) c = getchar() ;

    while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;

    return res ;

}

/*inline void clear(){ while (!s.empty()) s.pop() ; }*/

/*inline void remove(){

    for (int di = 1 ; di <= 5 ; ++ di)

        for (int dj = 1 ; dj <= 7 ; ++ dj)

            if (T[di][dj] != -1

                int cnt = 0 ;

                for (int ki = di + 1 ; ki <= 5 && T[ki][dj] == T[di][dj] ; ++ ki) ++ cnt, s.push((D){ki, dj}) ;

                for (int ki = di - 1 ; ki >= 1 && T[ki][dj] == T[di][dj] ; -- ki) ++ cnt, s.push((D){ki, dj}) ;

                for (int ki = dj + 1 ; ki <= 7 && T[di][ki] == T[di][dj] ; ++ ki) ++ cnt, s.push((D){di, ki}) ;

                for (int ki = dj - 1 ; ki >= 1 && T[di][ki] == T[di][dj] ; -- ki) ++ cnt, s.push((D){di, ki}) ;

                if (cnt + 1 >= 3){

                    color[T[di][dj]] -= cnt + 1 ;

                    while (!s.empty()) T[s.top().x][s.top().y] = -1, s.pop() ;

                    for (int ki = 1 ; ki <= 5 ; ++ ki)

                        if (T[ki][dj] == -1){

                            for (int k = dj ; k <= 7 && (T[ki][k] != -1 || k == dj) ; ++ k) T[ki][k] = T[ki][k + 1] ;

                            T[ki][0] -- ;

                        }

                }

                else clear() ;

            }

}*/

/*inline void down(){

    for (int di = 1 ; di <= 5 ; ++ di){

        int ttt = 0 ;

        for (int dj = 1 ; dj <= 7 ; ++ dj)

            if (T[di][dj] == -1){

                ++ ttt ;

                for (int k = dj ; k <= 7 ; ++ k) T[di][k] = T[di][k + 1] ;

            }

        T[di][0] = 7 - ttt ;

    }

}*/

inline void down(){//妙啊

    int ttt = 0 ;

    for(int di = 1 ; di <= 5 ; ++ di){

        ttt = 0 ;

        for(int dj = 1 ; dj <= 7 ; ++ dj)

            if(T[di][dj] == -1) ++ ttt ;

            else{

                if(! ttt) continue ;

                T[di][dj - ttt] = T[di][dj], T[di][dj] = -1 ;

            }

//        T[di][0] = 7 - ttt ;

    }

}

inline bool remove(){ // void -> bool

    bool Mark = 0 ;

    memset(Remove, 0, sizeof(Remove)) ;

    for (int di = 1 ; di <= 5 ; ++ di)

        for (int dj = 1 ; dj <= 7 ; ++ dj){

            if (T[di][dj] != -1 && di >= 2 && di <= 4 && T[di][dj] == T[di + 1][dj] && T[di][dj] == T[di - 1][dj]){

                Remove[di + 1][dj] = Remove[di - 1][dj] = Remove[di][dj] = 1, Mark = 1 ;

            }

            if (T[di][dj] != -1 && dj >= 2 && dj <= 6 && T[di][dj] == T[di][dj + 1] && T[di][dj] == T[di][dj - 1]){

                Remove[di][dj + 1] = Remove[di][dj - 1] = Remove[di][dj] = 1, Mark = 1 ;

            }

        }

    if (!Mark) return 0 ;

    for (int di = 1 ; di <= 5 ; ++ di)

        for (int dj = 1 ; dj <= 7 ; ++ dj)

            T[di][dj] = (!Remove[di][dj]) ? T[di][dj] : -1 ;

    down() ; return 1 ;

}

/*

inline void down(int x, int y, int d){

    if (d == 1){

        int k, temp = T[x][y] ;

        for (k = y ; k <= 7 && T[x][k] != -1 ; ++ k) T[x][k] = T[x][k + 1] ;

        for (k = y ; k >= 1 && T[x - 1][k - 1] == -1 ; -- k) ;

        T[x - 1][k] = temp ; T[x][0] --, T[x - 1][0] ++ ;

    }

    else {

        int k, temp = T[x][y] ;

        for (k = y ; k <= 7 && T[x][k] != -1 ; ++ k) T[x][k] = T[x][k + 1] ;

        for (k = y ; k >= 1 &&

         T[x + 1][k - 1] == -1 ; -- k) ;

        T[x + 1][k] = temp ; T[x][0] --, T[x + 1][0] ++ ;

    }

    remove() ; return ;

}*/

inline bool judge(){

    for (int di = 1 ; di <= 5 ; ++ di)

        for (int dj = 1 ; dj <= 7 ; ++ dj)

         	if (T[di][dj] != -1) return false ;

    return true ;

}

inline void _reset(int x){

    for (int di = 1 ; di <= 5 ; ++ di)

        for (int dj = 1 ; dj <= 7 ; ++ dj)

            T[di][dj] = base[x][di][dj] ;

}

inline void Prepare(int x){

    for (int di = 1 ; di <= 5 ; ++ di)

        for (int dj = 1 ; dj <= 7 ; ++ dj)

            base[x][di][dj] = T[di][dj] ;

}

inline void dfs_work(int step){

    if (judge()){

        for (int di = 1 ; di <= N ; ++ di)

            printf("%d %d %d\n", res[di].x, res[di].y, res[di].d) ;

        exit(0) ;

    }

    /*for (int di = 1 ; di <=5 ; ++ di)

        for (int dj = 1 ; dj <= 7 ; ++ dj)

            printf("%d%c", T[di][dj], " \n"[dj == 7]) ; */

    if (step == N + 1) return ;

    Prepare(step) ;

    for (int di = 1 ; di <= 5 ; ++ di)

        for (int dj = 1 ; dj <= 7 ; ++ dj){

            if (T[di][dj] == -1) break ;

            if (di > 1 && T[di - 1][dj] == -1){

                swap(T[di][dj], T[di - 1][dj]) ; down() ; while (remove()) ;//after exchange, need down

                res[step] = (Ans){di - 1, dj - 1, -1} ; dfs_work(step + 1) ; _reset(step) ; res[step] = (Ans){-1, -1, -1} ;

            }

            if (di < 5 && T[di][dj] != T[di + 1][dj]){

                swap(T[di][dj], T[di + 1][dj]) ; down() ; while(remove()) ;

                res[step] = (Ans){di - 1, dj - 1 ,1} ; dfs_work(step + 1) ; _reset(step) ; res[step] = (Ans){-1, -1, -1} ;

            }

        }

}

//problem1 : no reset -> correct

//problem1.5 : the same state -> ?

//problem2 : It's not a good way to search

//ERROR : Why is it broken? How to solve it?

int main(){

//	freopen("std.out", "w", stdout) ;

    cin >> N ; memset(T, -1, sizeof(T)) ;

    for (i = 1 ; i <= 5 ; ++ i) T[i][0] = 0 ;

    for (i = 1 ; i <= 5 ; ++ i)

        while((t = qr()) != 0) T[i][++ T[i][0]] = t ;

    dfs_work(1) ; cout << -1 << endl ; return 0 ;

}

随机推荐

  1. 利用zlib库进行zip解压

    1:到zlib官网上下载zlib,本文下载的是1.2.8的版本. 2:进行./configure,然后make. 3:进入zlib库中的contrib/minizip/路径下make,生成的miniz ...

  2. PS技能大全

    1.设置固定的图片大小 参考:http://jingyan.baidu.com/album/642c9d3418bec4644a46f72a.html?picindex=1

  3. sqlserver 导出数据字典

    -- 数据字典 SELECT ( then d.name else '' end)表名, a.colorder 字段序号, a.name 字段名, ( then '√'else '' end) 标识, ...

  4. Android 用户界面---拖放（Drag and Drop）（一）

    用Android的拖放框架,能够允许用户使用图形化的拖放手势,把数据从当前布局中的一个View对象中移到另一个View对象中.这个框架包括:拖拽事件类.拖拽监听器.以及辅助的方法和类. 尽管这个框架主 ...

  5. 浅谈 C&sol;S 和 B&sol;S 架构

    概述 在这个信息急剧膨胀的社会,我们不得不说人类正进入一个崭新的时代,那就是信息时代.信息时代的一个主要而显著的特征就是计算机网络的应用.计算机网络从最初的集中式计算,经过了Client/Server ...

  6. &lpar;luogu P3358&rpar;最长k可重区间集问题 &lbrack;TPLY&rsqb;

    最长k可重区间集问题 题目链接 https://www.luogu.org/problemnew/show/3358 做法 所有点向下一个点连容量为k费用为0的边 l和r连容量为1费用为区间长度的边 ...

  7. Android图表库MPAndroidChart&lpar;六&rpar;——换一种思考方式，水平条形图的实现过程

    Android图表库MPAndroidChart(六)--换一种思考方式,水平条形图的实现过程 一.基本实现 我们之前实现了条形图,现在来看下水平条形图是怎么实现的,说白了就是横起来,看下效果: 说起 ...

  8. 设计在canal中的运用，看到随手记下

    观察者模式,定义添加修改删除对应的操作 系统很多Monitor/Listener都是类似 Monitor内含listener,调用再触发 public synchronized void start( ...

  9. spring applicationContext&period;xml

    <?xml version="1.0" encoding="UTF-8"?><beans xmlns="http://www.spr ...

  10. Structs 2 session 学习

    后台获取 值类型  request.getSession().setAttribute("username", user.getUserName());  对象类型   reque ...

相关文章