#include"stdlib.h"
#include"stdio.h"
#define N 50
#define M 50
int X
int maze[N+2][M+2]
struct point{
int row,col,predecessor
}queue[512]
int head=0,tail=0
void shoudong_maze(int m,int n){
int i,j
printf("\n\n")
printf("请按行输入迷宫,0表示通路,1表示障碍:\n\n")
for(i=0i<mi++)
for(j=0j<nj++)
scanf("%d",&maze[i][j])
}
void zidong_maze(int m,int n){
int i,j
printf("\n迷宫生成中……\n\n")
system("pause")
for(i=0i<mi++)
for(j=0j<nj++)
maze[i][j]=rand()%2
//由于rand()产生的随机数是从0到RAND_MAX
//RAND_MAX是定义在stdlib.h中的,其值至少为32767)
//要产生从X到Y的数,只需要这样写:k=rand()%(Y-X+1)+X
}
void print_maze(int m,int n){
int i,j
printf("\n迷宫生成结果如下:\n\n")
printf("迷宫入口\n")
printf("↓")
for(i=0i<mi++)
{printf("\n")
for(j=0j<nj++)
{if(maze[i][j]==0) printf("□")
if(maze[i][j]==1) printf("■")}
}
printf("→迷宫出口\n")
}
void result_maze(int m,int n)
{ int i,j
printf("迷宫通路(用☆表示)如下所示:\n\t")
for(i=0i<mi++)
{ printf("\n")
for(j=0j<nj++)
{if(maze[i][j]==0||maze[i][j]==2) printf("□")
if(maze[i][j]==1) printf("■")
if(maze[i][j]==3) printf("☆")
}
}
}
void enqueue(struct point p)
{ queue[tail]=p
tail++
}
struct point dequeue()
{ head++
return queue[head-1]
}
int is_empty()
{ return head==tail
}
void visit(int row,int col,int maze[52][52])
{ struct point visit_point={row,col,head-1}
maze[row][col]=2
enqueue(visit_point)
}
int mgpath(int maze[52][52],int m,int n)
{ X=1
struct point p={0,0,-1}
if(maze[p.row][p.col]==1)
{ printf("\n===============================================\n")
printf("此迷宫无解\n\n")X=0return 0}
maze[p.row][p.col]=2
enqueue(p)
while(!is_empty())
{p=dequeue()
if((p.row==m-1)&&(p.col==n-1)) break
if((p.col+1<n)&&(maze[p.row][p.col+1]==0)) visit(p.row,p.col+1,maze)
if((p.row+1<m)&&(maze[p.row+1][p.col]==0)) visit(p.row+1,p.col,maze)
if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze)
if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze)
}
if(p.row==m-1&&p.col==n-1)
{printf("\n==================================================================\n")
printf("迷宫路径为:\n")
printf("(%d,%d)\n",p.row,p.col)
maze[p.row][p.col]=3
while(p.predecessor!=-1)
{p=queue[p.predecessor]
printf("(%d,%d)\n",p.row,p.col)
maze[p.row][p.col]=3
}
}
else {printf("\n=============================================================\n")
printf("此迷宫无解!\n\n")X=0}
return 0
}
int main()
{int i,m,n,cycle=0
while(cycle!=(-1))
{
printf("********************************************************************************\n")
printf(" ☆欢迎进入迷宫求解系统☆\n")
printf(" 设计者:尹旭 林静波(信息2班)\n")
printf("********************************************************************************\n")
printf(" 手动生成迷宫 请按:1\n")
printf(" 自动生成迷宫 请按:2\n")
printf(" 退出 请按:3\n\n")
printf("********************************************************************************\n")
printf("\n")
printf("请选择你的操作:\n")
scanf("%d",&i)
switch(i)
{case 1:printf("\n请输入行数:")
scanf("%d",&m)
printf("\n")
printf("请输入列数:")
scanf("%d",&n)
while((m<=0||m>50)||(n<=0||n>50))
{ printf("\n抱歉,你输入的行列数超出预设范围(0-50,0-50),请重新输入:\n\n")
printf("请输入行数:")
scanf("%d",&m)
printf("\n")
printf("请输入列数:")
scanf("%d",&n)
}
shoudong_maze(m,n)
print_maze(m,n)
mgpath(maze,m,n)
if(X!=0)
result_maze(m,n)
printf("\n\nPress Enter Contiue!\n")
getchar()
while(getchar()!='\n')
break
case 2:printf("\n请输入行数:")
scanf("%d",&m)
printf("\n")
printf("请输入列数:")
scanf("%d",&n)
while((m<=0||m>50)||(n<=0||n>50))
{printf("\n抱歉,你输入的行列数超出预设范围(0-50,0-50),请重新输入:\n\n")
printf("请输入行数:")
scanf("%d",&m)
printf("\n")
printf("请输入列数:")
scanf("%d",&n)
}
zidong_maze(m,n)
print_maze(m,n)
mgpath(maze,m,n)
if(X!=0)
result_maze(m,n)
printf("\n\nPress Enter Contiue!\n")getchar()while(getchar()!='\n')break
case 3:cycle=(-1)
break
default:printf("\n")
printf("你的输入有误!\n")
printf("\nPress Enter Contiue!\n")
getchar()
while(getchar()!='\n')break
}
}
}
package 走迷宫import java.awt.BorderLayout
import java.awt.Color
import java.awt.GridLayout
import java.awt.event.ActionEvent
import java.awt.event.ActionListener
import java.util.ArrayList
import java.util.LinkedList
import java.util.List
import java.util.TimerTask
import javax.swing.JButton
import javax.swing.JFrame
import javax.swing.JOptionPane
import javax.swing.JPanel
// 迷宫
public class Maze extends JFrame implements ActionListener {
private JPanel panel
private JPanel northPanel
private JPanel centerPanel
private MazeGrid grid[][]
private JButton restart
private JButton dostart
private int rows// rows 和cols目前暂定只能是奇数
private int cols
private List<String>willVisit
private List<String>visited
private LinkedList<String>comed
private long startTime
private long endTime
public Maze() {
rows = 25
cols = 25
willVisit = new ArrayList<String>()
visited = new ArrayList<String>()
comed = new LinkedList<String>()
init()
this.setTitle("回溯法--走迷宫")
this.add(panel)
this.pack()
this.setVisible(true)
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE)
}
public void init() {
panel = new JPanel()
northPanel = new JPanel()
centerPanel = new JPanel()
panel.setLayout(new BorderLayout())
restart = new JButton("重新生成迷宫")
dostart = new JButton("开始走迷宫")
grid = new MazeGrid[rows][cols]
centerPanel.setLayout(new GridLayout(rows, cols, 1, 1))
centerPanel.setBackground(new Color(0, 0, 0))
northPanel.add(restart)
northPanel.add(dostart)
dostart.addActionListener(this)
restart.addActionListener(this)
for (int i = 0i <grid.lengthi++)
for (int j = 0j <grid[i].lengthj++) {
if (j % 2 == 0 &&i % 2 == 0)
grid[i][j] = new MazeGrid(true, 20, 20)
else
grid[i][j] = new MazeGrid(false, 20, 20)
}
grid[0][0].setVisited(true)
grid[0][0].setPersonCome(true)
grid[0][0].setStart(true)
visited.add("0#0")
grid[rows - 1][cols - 1].setEnd(true)
grid = createMap(grid, 0, 0)
for (int i = 0i <grid.lengthi++)
for (int j = 0j <grid[i].lengthj++) {
grid[i][j].repaint()
centerPanel.add(grid[i][j])
}
panel.add(northPanel, BorderLayout.NORTH)
panel.add(centerPanel, BorderLayout.CENTER)
}
/**
* 生成迷宫
*
* @param mazeGrid
* @param x
* @param y
* @return
*/
public MazeGrid[][] createMap(MazeGrid mazeGrid[][], int x, int y) {
int visitX = 0
int visitY = 0
if (x - 2 >= 0) {
if (!mazeGrid[x - 2][y].isVisited()) {
willVisit.add((x - 2) + "#" + y)
}
}
if (x + 2 <cols) {
if (!mazeGrid[x + 2][y].isVisited()) {
willVisit.add((x + 2) + "#" + y)
}
}
if (y - 2 >= 0) {
if (!mazeGrid[x][y - 2].isVisited()) {
willVisit.add(x + "#" + (y - 2))
}
}
if (y + 2 <rows) {
if (!mazeGrid[x][y + 2].isVisited()) {
willVisit.add(x + "#" + (y + 2))
}
}
if (!willVisit.isEmpty()) {
int visit = (int) (Math.random() * willVisit.size())
String id = willVisit.get(visit)
visitX = Integer.parseInt(id.split("#")[0])
visitY = Integer.parseInt(id.split("#")[1])
mazeGrid[(visitX + x) / 2][(visitY + y) / 2].setMark(true)
mazeGrid[visitX][visitY].setVisited(true)
if (!visited.contains(id)) {// 将这个点加到已访问中去
visited.add(id)
}
willVisit.clear()
createMap(mazeGrid, visitX, visitY)
} else {
if (!visited.isEmpty()) {
String id = visited.remove(visited.size() - 1)// 取出最后一个元素
visitX = Integer.parseInt(id.split("#")[0])
visitY = Integer.parseInt(id.split("#")[1])
mazeGrid[visitX][visitY].setVisited(true)
createMap(mazeGrid, visitX, visitY)
}
}
return mazeGrid
}
/**
* 走迷宫
*
* @param mazeGrid
* @param x
* @param y
*/
public String goMaze(MazeGrid mazeGrid[][], int x, int y) {
int comeX = 0
int comeY = 0
// left
if (x - 1 >= 0) {
if (mazeGrid[x - 1][y].isMark()) {
if (!comed.contains((x - 1) + "#" + y))
willVisit.add((x - 1) + "#" + y)
}
}
// right
if (x + 1 <cols) {
if (mazeGrid[x + 1][y].isMark()) {
if (!comed.contains((x + 1) + "#" + y))
willVisit.add((x + 1) + "#" + y)
}
}
// up
if (y - 1 >= 0) {
if (mazeGrid[x][y - 1].isMark()) {
if (!comed.contains(x + "#" + (y - 1)))
willVisit.add(x + "#" + (y - 1))
}
}
// down
if (y + 1 <rows) {
if (mazeGrid[x][y + 1].isMark()) {
if (!comed.contains(x + "#" + (y + 1)))
willVisit.add(x + "#" + (y + 1))
}
}
if (!willVisit.isEmpty()) {
int visit = (int) (Math.random() * willVisit.size())
String id = willVisit.get(visit)
comeX = Integer.parseInt(id.split("#")[0])
comeY = Integer.parseInt(id.split("#")[1])
mazeGrid[x][y].setPersonCome(false)
mazeGrid[comeX][comeY].setPersonCome(true)
mazeGrid[x][y].repaint()
mazeGrid[comeX][comeY].repaint()
willVisit.clear()
comed.add(x + "#" + y)
} else {
if (!comed.isEmpty()) {
String id = comed.removeLast()
comeX = Integer.parseInt(id.split("#")[0])
comeY = Integer.parseInt(id.split("#")[1])
mazeGrid[x][y].setPersonCome(false)
mazeGrid[comeX][comeY].setPersonCome(true)
mazeGrid[x][y].repaint()
mazeGrid[comeX][comeY].repaint()
comed.addFirst(x + "#" + y)
}
}
return comeX + "#" + comeY
}
int comeX = 0
int comeY = 0
public void actionPerformed(ActionEvent e) {
if (e.getActionCommand().equals("重新生成迷宫")) {
refreshMap(grid)
} else if (e.getActionCommand().equals("开始走迷宫")) {
startTime = System.currentTimeMillis()
dostart.setVisible(false)
restart.setText("禁止刷新")
int delay = 1000
int period = 500// 循环间隔
java.util.Timer timer = new java.util.Timer()
timer.scheduleAtFixedRate(new TimerTask() {
public void run() {
if (grid[rows - 1][cols - 1].isPersonCome()) {
endTime = System.currentTimeMillis()
JOptionPane.showMessageDialog(null, "已经走出迷宫,耗时"
+ (endTime - startTime) / 1000 + "秒", "消息提示",
JOptionPane.ERROR_MESSAGE)
this.cancel()
restart.setText("重新生成迷宫")
} else {
String id = goMaze(grid, comeX, comeY)
comeX = Integer.parseInt(id.split("#")[0])
comeY = Integer.parseInt(id.split("#")[1])
}
}
}, delay, period)
}
}
/**
* 刷新地图
*/
public void refreshMap(MazeGrid mazeGrid[][]) {
comeX = 0
comeY = 0
willVisit.clear()
visited.clear()
comed.clear()
this.remove(panel)
init()
this.add(panel)
this.pack()
this.setVisible(true)
}
public static void main(String args[]) {
long start = System.currentTimeMillis()
new Maze()
long end = System.currentTimeMillis()
System.out.println("使用ArrayList生成迷宫耗时:" + (end - start) + "毫秒")
}
}
Java走迷宫的源代码,能运行就行已经上传附件楼主可以在附件下载
手机是看不到附件的可以电脑直接下载。
如果尤文记得采纳哦!!!