Tetris DFS算法练习
2021/11/24 14:10:30
本文主要是介绍Tetris DFS算法练习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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算法练习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南