PuyoPuyo DFS算法练习

PuyoPuyo DFS算法练习

题目和解析有空再整理。

package puyopuyo;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/21 11:18
 * @Description
 * @Since version-1.0
 */
public class Block {

    /**
     * 状态
     */
    int event = 0;
    /**
     * 方向
     */
    int dir = 0;

    /**
     * 列号
     */
    int col = 0;
    /**
     * 颜色
     */
    int[] val;

    public Block(int[] val) {
        this.val = val;
    }
}

package puyopuyo;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/21 13:00
 * @Description
 * @Since version-1.0
 */
public class Point {
    int x = 0;
    int y = 0;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public Point() {
    }
}

package puyopuyo;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/21 17:36
 * @Description
 * @Since version-1.0
 */
public class Demo02 {
    /**
     * 宽度
     */
    private static int width = 4;
    /**
     * 高度
     */
    private static int height = 6;
    /**
     * 地图
     */
    private static int[][] map = new int[height][width];
    /**
     * 标记图
     */
    private static int[][] mark = new int[height][width];
    /**
     * 列的高度,y坐标
     */
    private static int[] tail = new int[width];
    private static int[] dirX = {1,0,-1,0};
    private static int[] dirY = {0,1,0,-1};
    /**
     * 当前块
     */
    private static Block block;
    /**
     * 地图初始化
     */
    private static void inti(int w){
        width = w;
        map = new int[height][width];
    }
    /**
     * 旋转一个角度
     * @param angle
     */
    private static void rotate(int angle){
        block.dir=(block.dir+angle)%4;
        //右边界
        if (block.dir==0&&block.col==width-1){
            block.col=width-2;
        }
        if (block.dir==2&&block.col==0){
            block.col=1;
        }
    }
    /**
     * 移动一段距离
     * @param distance
     */
    private static void move(int distance){
        block.col+=distance;
        //中间区域不用考虑
        if (block.col>=1 && block.col<=width-2){
            return;
        }
        //右方向看右边界
        if (block.dir==0 && block.col>=width-1){
            block.col=width-2;
            return;
        }
        //左方向看左边界
        if (block.dir==2 && block.col<=0){
            block.col=1;
            return;
        }
        //其他方向右越界(dis过大)
        if (block.col > width-1){
            block.col = width-1;
        }
        //其他方向左越界(dis过大)
        if (block.col < 0){
            block.col = 0;
        }
    }
    private static void hinder(int count,int life){
       // block.event = 2;
        int h = height-1;
        for (int i = 0; i < count; i++) {
            map[h-tail[i]][i] = -1*life;
            tail[i]++;
        }
    }
    /**
     * 更新当前块下落后的地图,记录列高度
     * @return
     */
    private static int land(){
        //1.将一个圆叠在另一个圆上,不留空隙。
        Point p1 = new Point();
        Point p2 = new Point();
        int h = height-1;
        if (block.event==0){
            switch (block.dir){
                case 0:
                {
                    p1.x = block.col;
                    p1.y = h-tail[block.col];
                    map[p1.y][p1.x] = block.val[0];
                    p2.x = block.col+1;
                    p2.y = h-tail[block.col];
                    map[p2.y][p2.x] = block.val[1];
                    tail[block.col]++;
                    tail[block.col+1]++;
                    break;
                }
                case 1:
                {
                    p1.x = block.col;
                    p1.y = h-(tail[block.col]+1);
                    map[p1.y][p1.x] = block.val[0];
                    p2.x = block.col;
                    p2.y = h-tail[block.col];
                    map[p2.y][p2.x] = block.val[1];
                    tail[block.col]+=2;
                    break;
                }
                case 2:
                {
                    p1.x = block.col;
                    p1.y = h-tail[block.col];
                    map[p1.y][p1.x] = block.val[0];
                    p2.x = block.col-1;
                    p2.y = h-tail[block.col-1];
                    map[p2.y][p2.x] = block.val[1];
                    tail[block.col]++;
                    tail[block.col-1]++;
                    break;
                }
                case 3:
                {
                    p1.x = block.col;
                    p1.y = h-tail[block.col];
                    map[p1.y][p1.x] = block.val[0];
                    p2.x = block.col;
                    p2.y = h-(tail[block.col]+1);
                    map[p2.y][p2.x] = block.val[1];
                    tail[block.col]+=2;
                    break;
                }
                default:
                    break;
            }
            solution(p1,p2);
        }
        int j=0;
        for (int i = 0; i < width; i++) {
            j= Math.max(tail[i], j);
        }
        return j;
    }
    private static Point[] drop = new Point[width*height];

    /**
     * 块下落后的消除
     * @param p1
     * @param p2
     */
    private static void solution(Point p1,Point p2){
        int dropNum = 2;
        drop[0] = p1;
        drop[1] = p2;

        while (dropNum!=0){
            for (int i = 0; i < dropNum; i++) {
                //一组两个颜色相同
                if (mark[drop[i].y][drop[i].x] == 1){
                    continue;
                }
                dfs(drop[i].x,drop[i].y);
                clear();
            }
            markHinder();
            dropNum = updateMap();
        }
    }
    private static Stack<Point> elimP = new Stack<>();
    private static int[][] mark2 = new int[height][width];

    /**
     * 搜索4个同色相连块,放入搜索队列
     * @param x
     * @param y
     */
    private static void dfs(int x,int y){
        mark2[y][x] = 1;
        elimP.push(new Point(x,y));
        for (int i = 0; i < 4; i++) {
            int a = x+dirX[i];
            int b = y+dirY[i];
            if (a>=0&&a<width&&b>=0&&b<height&&map[b][a]==map[y][x]&&mark2[b][a]==0){
                dfs(a,b);
            }
        }
    }

    /**
     * 根据搜索结果清理同色块
     */
    private static void clear(){
        int s = elimP.size();
        if (s>=4){
            for (int i = 0; i < s; i++) {
                Point p = elimP.pop();
                map[p.y][p.x]=0;
                mark[p.y][p.x]=1;
                tail[p.x]--;
            }
        }
        elimP.removeAllElements();

    }
    /**
     * 消除同色块后,更新阻碍块寿命和位置,顺便消除标记
     */
    private static void markHinder(){
        int h = height-1;
        for (int i = 0; i < width; i++) {
            for (int j = 0; j <= tail[i]; j++) {
                if (map[h-j][i]<0){
                    if (check(h-j,i)==1){
                        map[h-j][i] += 1;
                        if (map[h-j][i]==0){
                            tail[i]--;
                        }
                    }
                }
            }
        }
        mark2 = new int[height][width];
        mark = new int[height][width];
    }

    /**
     * 同色块消除后,把空中的块放下来,顺便放入搜索队列
     * @return 空中块的数量
     */
    private static int updateMap(){
        int c = 0;
        int s = 0;
        int sum = 0;
        int h = height-1;
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < tail[i]; j++) {
                int l = h-j;
                if (map[l][i]==0){
                    if (j>=tail[i]){
                        break;
                    }
                    //j=1,c=3
                    while (map[l-c][i]==0&&j+c<tail[i]){
                        c++;
                    }
                    if (j+c+1==tail[i]){
                        tail[i]=j;
                        break;
                    }
                    if (map[l-c][i]>0) {
                        map[l][i] = map[l - c][i];
                        map[l - c][i] = 0;
                        drop[s].x = i;
                        drop[s++].y = l;
                        sum++;
                    }
                    if (map[l-c][i]<0) {
                        map[l][i] = map[l - c][i];
                        map[l - c][i] = 0;
                    }
                }
            }
        }
        return sum;

    }

    /**
     * 查看阻碍块四周是否有爆裂的同色块
     * @param y
     * @param x
     * @return
     */
    private static int check(int y,int x){
        for (int i = 0; i < 4; i++) {
            int a = y+dirY[i];
            int b = x+dirX[i];
            if (a>=0&&b>=0&&a<height&&b<width&&mark[a][b]==1){
                return 1;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int sum = 0;
        block = new Block(new int[]{1,1});
        rotate(0);
        move(1);
        sum = land();
        hinder(2,2);
        hinder(4,1);
        block = new Block(new int[]{2,2});
        rotate(0);
        move(2);
        sum = land();
        block = new Block(new int[]{1,1});
        rotate(1);
        move(2);
        sum = land();
        block = new Block(new int[]{2,2});
        rotate(1);
        move(3);
        sum = land();

        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (map[i][j]<0){
                    System.out.print(map[i][j]);
                }else {
                    System.out.print(" "+map[i][j]);
                }
                if (j==width-1){
                    System.out.println();
                }
            }
        }
        System.out.println("最高列长度是:"+sum);
    }
}

负数代表阻碍块生命值,正数代表颜色,0为空

打印一下过程:

 0 0 0 0
 0 0 0 0
 0 0 0 0
 0 0 0 0
 0 0 0 0
 0 1 1 0
最高列长度是:1

 0 0 0 0
 0 0 0 0
 0 0 0 0
 0-1 2 0
-1-2-1 2
-2 1 1-1
最高列长度是:3

 0 0 0 0
 0 0 1 0
 0 0 1 0
 0-1 2 0
-1-2-1 2
-2 1 1-1
最高列长度是:5

 0 0 0 0
 0 0 0 0
 0 0 0 0
 0 0 0 0
-1 0 0 0
-1-1 0 0
最高列长度是:2
上一篇:剑指 day 3【JZ52 两个链表的第一个公共结点】增加链表长度以使双指针起效


下一篇:C语言从入门到入土(入门篇)(算法篇p2)汉罗塔与青蛙跳台阶的递归实现(及扩展青蛙跳台阶)