Tetris DFS算法练习(Tetris DFS algorithm exercise)

Tetris DFS算法练习

题目和分析有空再整理

package tetris;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/22 16:46
 * @Description
 * @Since version-1.0
 */
public class Block {
    /**
     * 状态,0为普通块,1为特殊块。
     */
    int event = 0;
    /**
     * 列数
     */
    int col = 0;
    /**
     * 颜色
     */
    int[] val;
    /**
     * 特殊块类型
     */
    int type;
    public Block(int[] val){
        this.val = val;
    }
    public Block(int event,int type){
        this.event = event;
        this.type = type;
    }
}

package tetris;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/22 17:23
 * @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 tetris;

import java.util.Stack;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/22 16:44
 * @Description
 * @Since version-1.0
 */
public class Demo02 {
    private static int width = 5;
    private static int height = 10;
    private static int[][] map = new int[width][height];
    private static int[][] mark1 = new int[width][height];
    private static int[][] mark2 = new int[width][height];
    private static Block block;
    private static int[] tail = new int[height];
    private static Point[] drop = new Point[width*height];

    /**
     * 跑马灯移动数组
     * @param num 移动位数
     */
    private static void rotate(int num){
        if (num == 1){
            int temp = 0;
            temp = block.val[0];
            block.val[0] = block.val[2];
            block.val[2] = block.val[1];
            block.val[1] = temp;
        }
        if (num == 2){
            int temp = 0;
            temp = block.val[0];
            block.val[0] = block.val[1];
            block.val[1] = block.val[2];
            block.val[2] = temp;
        }
    }

    /**
     * 移动
     * @param distance
     */
    private static void move(int distance){
        block.col+=distance;
        if (block.col>=width){
            block.col=width-1;
        }
        if (block.col<0){
            block.col=0;
        }
    }

    /**
     * 块落地后的坐标
     * @param args
     */
    private static void simpleLand(){
        if (block.event==0){
            drop[0]=new Point(block.col,tail[block.col]++);
            drop[1]=new Point(block.col,tail[block.col]++);
            drop[2]=new Point(block.col,tail[block.col]++);
            map[drop[0].x][drop[0].y] = block.val[2];
            map[drop[1].x][drop[1].y] = block.val[1];
            map[drop[2].x][drop[2].y] = block.val[0];
           // int dropNum = 3;
            solution(3);
        }
    }
    private static void solution(int dropNum){
        while (dropNum!=0){
            for (int i = 0; i < dropNum; i++) {
                if (map[drop[i].x][drop[i].y]==0){
                    continue;
                }
                dfs1(drop[i].x,drop[i].y);
                clear();
            }
            dropNum = updateMap();
        }
    }
    private static int[] dirX = {0,1,1,1,0,-1,-1,-1};
    private static int[] dirY = {1,1,0,-1,-1,-1,0,1};
    /**
     * 消除点集
     */
    private static Stack<Point> eliminate = new Stack<>();

    /**
     *
     * @param x
     * @param y
     */
    private static void dfs1(int x, int y){
        Stack<Point> temp = new Stack<>();
        if (map[x][y]!=0){
            for (int i = 0; i < 4; i++) {
                int l = i;
                int k = 0;
                int a = x;
                int b = y;
                while (k!=2){
                    a+=dirX[l];
                    b+=dirY[l];
                    if (a>=0&&b>=0&&a<width&&b<height&&map[x][y]==map[a][b]&& mark1[a][b]==0){
                        mark1[a][b]=1;
                        temp.push(new Point(a,b));
                    }else {
                        k++;
                        l+=4;
                        a=x;
                        b=y;
                    }
                }
                int s = temp.size();
                if (s>=2&& mark1[x][y]==0){
                    mark1[x][y]=1;
                    eliminate.push(new Point(x,y));

                }
                for (int j = 0; j < s; j++) {
                    Point p = temp.pop();
                    if (s>=2){
                        eliminate.push(p);
                        dfs1(p.x,p.y);
                    }
                    //回溯
                    mark1[p.x][p.y]=0;
                }
            }
            mark1[x][y]=0;
        }
    }
    private static void specialLand(){
        int x = block.col;
        int y = tail[block.col]-1;
        if (block.type==1){
            int color = map[x][y];
            for (int i = 0; i < width; i++) {
                int h = tail[i];
                for (int j = 0; j < h; j++) {
                    if (map[i][j]==color){
                        map[i][j]=0;
                        tail[i]--;
                    }
                }
            }
        }

        if (block.type==2){
            dfs2(x,y);
            clear();
        }
        int d = updateMap();
        solution(d);
    }

    private static void dfs2(int x,int y){
        eliminate.push(new Point(x,y));
        mark2[x][y]=1;
        for (int i = 0; i < 8; i++) {
            int a = x+dirX[i];
            int b = y+dirY[i];
            if (a>=0&&b>=0&&a<width&&b<height&&map[a][b]==map[x][y]&& mark2[a][b]==0){
                dfs2(a,b);
            }
        }
    }

    /**
     * 根据搜索结果清理同色块
     */
    private static void clear(){
        int s = eliminate.size();
        for (int i = 0; i < s; i++) {
            Point p = eliminate.pop();
           // System.out.println("clear:map["+p.x+"]["+p.y+"]   ");
            if (map[p.x][p.y]!=0){
                map[p.x][p.y]=0;
                tail[p.x]--;
            }

        }
        mark1 = new int[width][height];
        mark2 = new int[width][height];
        eliminate.removeAllElements();
    }

    /**
     * 更新块下落后的地图
     */
    private static int updateMap(){
        //下落数组下标,把所有下落的块按顺序放入下落数组
        int a = 0;
        //记录下落块数
        int sum = 0;
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < tail[i]; j++) {
                if (map[i][j]==0){
                    //下落高度
                    int h = 1;
                    while (map[i][j+h]==0&&j+h<height){
                        h++;
                    }
                    map[i][j] = map[i][j + h];
                    map[i][j + h] = 0;
                    drop[a++] = new Point(i, j);
                    sum++;
                }
            }
        }
        return sum;
    }


    private static void newSimpleBlock(int a, int b, int c){
        block = new Block(new int[]{a,b,c});
    }
    private static void newSpecialBlock(int type){
        block = new Block(1,type);
    }
    public static void main(String[] args) {
        newSimpleBlock(1,3,2);
        move(0);
        simpleLand();
        newSimpleBlock(3,4,2);
        move(1);
        simpleLand();
        newSimpleBlock(2,5,3);
        move(3);
        simpleLand();
        newSimpleBlock(5,3,2);
        move(2);
        simpleLand();
        newSimpleBlock(2,5,2);
        move(4);
        simpleLand();
        newSpecialBlock(2);
        move(3);
        specialLand();
        newSimpleBlock(1,2,1);
        move(2);
        simpleLand();
        newSpecialBlock(1);
        specialLand();

        for (int i = height-1; i >= 0; i--) {
            for (int j = 0; j < width; j++) {

                System.out.print(" "+map[j][i]+" ");
                if (j== width -1){
                    System.out.println();
                }
            }
        }
    }
}


打印过程:

 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  0  0  0  0 
 3  0  0  0  0 
 2  0  0  0  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  3  0  0  0 
 3  4  0  0  0 
 2  2  0  0  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  3  0  2  0 
 3  4  0  5  0 
 2  2  0  3  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  0  0  2  0 
 3  4  5  5  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  2 
 1  0  0  2  5 
 3  4  5  5  2 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  0  0  0  0 
 3  4  0  0  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  1  0  0 
 1  0  2  0  0 
 3  4  1  0  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 3  4  2  0  0 
————————

Tetris DFS算法练习

Topics and analysis will be reorganized when available

package tetris;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/22 16:46
 * @Description
 * @Since version-1.0
 */
public class Block {
    /**
     * 状态,0为普通块,1为特殊块。
     */
    int event = 0;
    /**
     * 列数
     */
    int col = 0;
    /**
     * 颜色
     */
    int[] val;
    /**
     * 特殊块类型
     */
    int type;
    public Block(int[] val){
        this.val = val;
    }
    public Block(int event,int type){
        this.event = event;
        this.type = type;
    }
}

package tetris;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/22 17:23
 * @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 tetris;

import java.util.Stack;

/**
 * @Author jinjun99
 * @Date Created in 2021/11/22 16:44
 * @Description
 * @Since version-1.0
 */
public class Demo02 {
    private static int width = 5;
    private static int height = 10;
    private static int[][] map = new int[width][height];
    private static int[][] mark1 = new int[width][height];
    private static int[][] mark2 = new int[width][height];
    private static Block block;
    private static int[] tail = new int[height];
    private static Point[] drop = new Point[width*height];

    /**
     * 跑马灯移动数组
     * @param num 移动位数
     */
    private static void rotate(int num){
        if (num == 1){
            int temp = 0;
            temp = block.val[0];
            block.val[0] = block.val[2];
            block.val[2] = block.val[1];
            block.val[1] = temp;
        }
        if (num == 2){
            int temp = 0;
            temp = block.val[0];
            block.val[0] = block.val[1];
            block.val[1] = block.val[2];
            block.val[2] = temp;
        }
    }

    /**
     * 移动
     * @param distance
     */
    private static void move(int distance){
        block.col+=distance;
        if (block.col>=width){
            block.col=width-1;
        }
        if (block.col<0){
            block.col=0;
        }
    }

    /**
     * 块落地后的坐标
     * @param args
     */
    private static void simpleLand(){
        if (block.event==0){
            drop[0]=new Point(block.col,tail[block.col]++);
            drop[1]=new Point(block.col,tail[block.col]++);
            drop[2]=new Point(block.col,tail[block.col]++);
            map[drop[0].x][drop[0].y] = block.val[2];
            map[drop[1].x][drop[1].y] = block.val[1];
            map[drop[2].x][drop[2].y] = block.val[0];
           // int dropNum = 3;
            solution(3);
        }
    }
    private static void solution(int dropNum){
        while (dropNum!=0){
            for (int i = 0; i < dropNum; i++) {
                if (map[drop[i].x][drop[i].y]==0){
                    continue;
                }
                dfs1(drop[i].x,drop[i].y);
                clear();
            }
            dropNum = updateMap();
        }
    }
    private static int[] dirX = {0,1,1,1,0,-1,-1,-1};
    private static int[] dirY = {1,1,0,-1,-1,-1,0,1};
    /**
     * 消除点集
     */
    private static Stack<Point> eliminate = new Stack<>();

    /**
     *
     * @param x
     * @param y
     */
    private static void dfs1(int x, int y){
        Stack<Point> temp = new Stack<>();
        if (map[x][y]!=0){
            for (int i = 0; i < 4; i++) {
                int l = i;
                int k = 0;
                int a = x;
                int b = y;
                while (k!=2){
                    a+=dirX[l];
                    b+=dirY[l];
                    if (a>=0&&b>=0&&a<width&&b<height&&map[x][y]==map[a][b]&& mark1[a][b]==0){
                        mark1[a][b]=1;
                        temp.push(new Point(a,b));
                    }else {
                        k++;
                        l+=4;
                        a=x;
                        b=y;
                    }
                }
                int s = temp.size();
                if (s>=2&& mark1[x][y]==0){
                    mark1[x][y]=1;
                    eliminate.push(new Point(x,y));

                }
                for (int j = 0; j < s; j++) {
                    Point p = temp.pop();
                    if (s>=2){
                        eliminate.push(p);
                        dfs1(p.x,p.y);
                    }
                    //回溯
                    mark1[p.x][p.y]=0;
                }
            }
            mark1[x][y]=0;
        }
    }
    private static void specialLand(){
        int x = block.col;
        int y = tail[block.col]-1;
        if (block.type==1){
            int color = map[x][y];
            for (int i = 0; i < width; i++) {
                int h = tail[i];
                for (int j = 0; j < h; j++) {
                    if (map[i][j]==color){
                        map[i][j]=0;
                        tail[i]--;
                    }
                }
            }
        }

        if (block.type==2){
            dfs2(x,y);
            clear();
        }
        int d = updateMap();
        solution(d);
    }

    private static void dfs2(int x,int y){
        eliminate.push(new Point(x,y));
        mark2[x][y]=1;
        for (int i = 0; i < 8; i++) {
            int a = x+dirX[i];
            int b = y+dirY[i];
            if (a>=0&&b>=0&&a<width&&b<height&&map[a][b]==map[x][y]&& mark2[a][b]==0){
                dfs2(a,b);
            }
        }
    }

    /**
     * 根据搜索结果清理同色块
     */
    private static void clear(){
        int s = eliminate.size();
        for (int i = 0; i < s; i++) {
            Point p = eliminate.pop();
           // System.out.println("clear:map["+p.x+"]["+p.y+"]   ");
            if (map[p.x][p.y]!=0){
                map[p.x][p.y]=0;
                tail[p.x]--;
            }

        }
        mark1 = new int[width][height];
        mark2 = new int[width][height];
        eliminate.removeAllElements();
    }

    /**
     * 更新块下落后的地图
     */
    private static int updateMap(){
        //下落数组下标,把所有下落的块按顺序放入下落数组
        int a = 0;
        //记录下落块数
        int sum = 0;
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < tail[i]; j++) {
                if (map[i][j]==0){
                    //下落高度
                    int h = 1;
                    while (map[i][j+h]==0&&j+h<height){
                        h++;
                    }
                    map[i][j] = map[i][j + h];
                    map[i][j + h] = 0;
                    drop[a++] = new Point(i, j);
                    sum++;
                }
            }
        }
        return sum;
    }


    private static void newSimpleBlock(int a, int b, int c){
        block = new Block(new int[]{a,b,c});
    }
    private static void newSpecialBlock(int type){
        block = new Block(1,type);
    }
    public static void main(String[] args) {
        newSimpleBlock(1,3,2);
        move(0);
        simpleLand();
        newSimpleBlock(3,4,2);
        move(1);
        simpleLand();
        newSimpleBlock(2,5,3);
        move(3);
        simpleLand();
        newSimpleBlock(5,3,2);
        move(2);
        simpleLand();
        newSimpleBlock(2,5,2);
        move(4);
        simpleLand();
        newSpecialBlock(2);
        move(3);
        specialLand();
        newSimpleBlock(1,2,1);
        move(2);
        simpleLand();
        newSpecialBlock(1);
        specialLand();

        for (int i = height-1; i >= 0; i--) {
            for (int j = 0; j < width; j++) {

                System.out.print(" "+map[j][i]+" ");
                if (j== width -1){
                    System.out.println();
                }
            }
        }
    }
}


Printing process:

 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  0  0  0  0 
 3  0  0  0  0 
 2  0  0  0  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  3  0  0  0 
 3  4  0  0  0 
 2  2  0  0  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  3  0  2  0 
 3  4  0  5  0 
 2  2  0  3  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  0  0  2  0 
 3  4  5  5  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  2 
 1  0  0  2  5 
 3  4  5  5  2 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 1  0  0  0  0 
 3  4  0  0  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  1  0  0 
 1  0  2  0  0 
 3  4  1  0  0 
 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 0  0  0  0  0 
 3  4  2  0  0