LWC 57:723. Candy Crush

LWC 57:723. Candy Crush

传送门:723. Candy Crush

Problem:

This question is about implementing a basic elimination algorithm for Candy Crush. Given a 2D integer array board representing the grid of candy, different positive integers board[i][j] represent different types of candies. A value of board[i][j] = 0 represents that the cell at position (i, j) is empty. The given board represents the state of the game following the player’s move. Now, you need to restore the board to a stable state by crushing candies according to the following rules:

  • If three or more candies of the same type are adjacent vertically or horizontally, “crush” them all at the same time - these positions become empty.
  • After crushing all candies simultaneously, if an empty space on the board has candies on top of itself, then these candies will drop until they hit a candy or bottom at the same time. (No new candies will drop outside the top boundary.)
  • After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps.
  • If there does not exist more candies that can be crushed (ie. the board is stable), then return the current board.

You need to perform the above rules until the board becomes stable, then return the current board.

Example 1:

Input: [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]] Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]] Explanation:

Note:

The length of board will be in the range [3, 50].

The length of board[i] will be in the range [3, 50].

Each board[i][j] will initially start as an integer in the range [1, 2000].

思路: 这不就是开心消消乐么,思路很直接,只要根据列和行检测出连续三个以上的块后,记录下来,消去,并继续更新,直到找不到连续三个块为止。

代码如下:

    public int[][] candyCrush(int[][] board) {
        int n = board.length;
        int m = board[0].length;
        boolean[][] next = new boolean[n][m];
        while (getNext(next, board)){
            List<Integer>[] ans = new ArrayList[m];
            for (int i = 0; i < m; ++i){
                ans[i] = new ArrayList<>();
                for (int j = n - 1; j >= 0; --j){
                    if (!next[j][i]) ans[i].add(board[j][i]);
                }
            }
            board = new int[n][m];
            // 重写
            for (int j = 0; j < m; ++j){
                for (int i = 0; i < ans[j].size(); ++i){
                    board[n - 1 - i][j] = ans[j].get(i);
                }
            }
            next = new boolean[n][m];
        }
        return board;
    }

    public boolean getNext(boolean[][] next, int[][] board){
        boolean exist = false;
        // 遍历行        
        int n = board.length;
        int m = board[0].length;

        for (int i = 0; i < n; ++i){
            int prev = board[i][0];
            int count = 1;
            for (int j = 1; j < m; ++j){
                if (board[i][j] == prev && board[i][j] != 0){
                    count ++;
                }   
                else{
                    if (count >= 3){
                        for (int l = 0; l < count; ++l){
                            next[i][j - 1 - l] = true;
                        }
                        exist = true;
                    }
                    count = 1;          
                }
                prev = board[i][j];
            }

            if (count >= 3){
                for (int l = 0; l < count; ++l){
                    next[i][m - 1 - l] = true;
                }
                exist = true;
            }
        }

        // 遍历列
        for (int i = 0; i < m; ++i){
            int prev = board[0][i];
            int count = 1;
            for (int j = 1; j < n; ++j){
                if (board[j][i] == prev && board[j][i] != 0){
                    count ++;
                }
                else{
                    if (count >= 3){
                        for (int l = 0; l < count; ++l){
                            next[j - 1 - l][i] = true;
                        }
                        exist = true;
                    }
                    count = 1;
                }
                prev = board[j][i];
            }

            if (count >= 3){
                    for (int l = 0; l < count; ++l){
                        next[n - 1 - l][i] = true;
                    }
                    exist = true;
            }
        }


        return exist;        
    }    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏奔跑的蛙牛技术博客

利用接口集合实现简单算法

953
来自专栏算法修养

PAT 1017 Queueing at Bank (模拟)

1017. Queueing at Bank (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

2687
来自专栏算法修养

UESTC 485 Game(康托,BFS)

Today I want to introduce an interesting game to you. Like eight puzzle, it is a...

2587
来自专栏TungHsu

这或许是对小白最友好的python入门了吧——10,元组

元组和列表差不多,但是和列表又不一样,除了长得不一样外,还有一个很大的不同就是元组的元素不能修改。 元组是这样写的(以矩形的长宽为例): rectangle =...

2684
来自专栏james大数据架构

JQuery实现仿sina新浪微博新鲜事滚动

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.or...

1727
来自专栏开源优测

python selenium2 - webelement操作常用方法

完整路径 C:\Python27\Lib\site-packages\selenium\webdriver\remote\webelement...

2755
来自专栏算法修养

PAT 甲级 1078 Hashing

1078. Hashing (25) 时间限制 100 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 ...

2846
来自专栏mathor

LeetCode138. 复制带随机指针的链表

 第一步:复制结点,复制的结点放在待复制的结点后,依然组成一个单链表  第二步:串接随机指针  第三步:将原单链表与复制链表拆开

522
来自专栏程序生活

Leetcode-Medium 338. Counting Bits题目描述代码实现

题目描述 Given a non negative integer number num. For every numbers i in the range ...

2395
来自专栏算法修养

PAT 1013 Battle Over Cities(并查集)

1013. Battle Over Cities (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 ...

2826

扫码关注云+社区