您现在的位置是：主页 > news > 南宁网站建设 传导/爱站网关键词搜索
南宁网站建设 传导/爱站网关键词搜索
admin2025/5/25 10:05:13【news】
简介南宁网站建设 传导,爱站网关键词搜索,门户建设目标,二级区域网站名迷宫分析：在一个封闭的空间内，用’0’表示可走，’1’表示墙；有一个起点和一个终点，需要找到从起点到终点的通路，还要保证在寻路的过程中不会出现来回走的情况。从起点出发，我们用0,1,2,3来表示上…
迷宫分析：在一个封闭的空间内，用’0’表示可走，’1’表示墙；有一个起点和一个终点，需要找到从起点到终点的通路，还要保证在寻路的过程中不会出现来回走的情况。从起点出发，我们用0,1,2,3来表示上下左右，也就是寻路的方向；每走一步之后都按照0,1,2,3的方向进行试探可否走，如果能走，把能走的坐标和来时的方向进行压栈，栈里都是走过的路线，如果0不通走1,1不通走2,2不通走3，都不通退一格，继续按照0-->1-->2-->3的方向寻路。这就很符合栈的先进后出原理，坐标点在栈里的存储可以用数组实现，也可以用链表实现，这里使用链表。存放坐标和方向使用类的数组，好像叫什么结构体，习惯性叫类的数组。
注意：每走一步的时候有几个不能走
1.不是’0’不能走
2.走过的不能走。(也就是栈里已经有的坐标点)
3.退回来的不能走(就是从栈里pop出的点)
栈：
package 栈原理迷宫游戏;
public class Stack {
public LinkList ll = new LinkList();
public int top;
public Stack(){
}
public void push(Data data){
ll.addHeadNode(data);
}
public void pop(){
ll.delNode();
}
public void print(){
ll.print();
}
public Data getNextNode(){
if(ll.head.getNext()!=null){
return ll.head.getNext().data;
}
return null;
}
public boolean isEmpty(){
if(ll.head==null){
return true;
}
return false;
}
public Data look(){
if(isEmpty()!=true){
return ll.head.data;
}
return null;
}
public boolean find(Data data){
if(isEmpty()){
return false;
}else{
return ll.findNode(data);
}
}
}
链表：
package 栈原理迷宫游戏;
public class LinkList {
public Node head;
public Node tail;
public LinkList(Node head,Node tail){
this.head = null;
this.tail = null;
}
public LinkList(){
}
//此时为了与栈相对应采用头插法添加
public void addHeadNode(Data data){
Node node = new Node (data, null, null);
if(head==null){
head = node;
head.setFront(null);
tail = node ;
tail.setNext(null);
}else{
head.setFront(node);
node.setNext(head);
head = node;
head.setFront(null);
}
}
//删除节点,为了与栈对应，每次删除的都是头节点
public void delNode(){
if(head!=null){
head = head.getNext();
head.setFront(null);
}
}
public boolean findNode(Data data){
if(head!=null){
Node temp=head;
while(temp!=null){
if(temp.data.equals(data)){
return true;
}
temp=temp.getNext();
}
}
return false;
}
public void print(){
if(head!=null){
Node temp=head;
while(temp!=null){
System.out.println(temp.data.x + " " + temp.data.y + " " + temp.data.f);
temp=temp.getNext();
}
}
}
}
class Node{
public Data data;
public Node front;
public Node next;
public Node (Data data, Node front, Node next){
this.data=data;
this.front=null;
this.next=null;
}
public Node (){
}
public void setData(Data data){
this.data = data;
}
public Data getData(){
return data;
}
public void setFront(Node front){
this.front = front;
}
public Node getFront(){
return front;
}
public void setNext(Node next){
this.next = next;
}
public Node getNext(){
return next;
}
}
类的数组：//存放走的路径和方向
package 栈原理迷宫游戏;
public class Data {
public int x;//横坐标
public int y;//纵坐标
public int f;//行走方向，0，1，2，3分别表示东西南北四个方向
public boolean equals(Data a){
if(a.x==x&&a.y==y){
return true;
}
return false;
}
}
Main:
package 栈原理迷宫游戏;
import java.io.FileReader;
import java.io.IOException;
/**
*❶@
*⓿
* ❶❶❶❶❶❶❶❶❶❶
* ❶⓿⓿❶⓿⓿⓿❶⓿❶
* ❶⓿⓿❶⓿⓿⓿❶⓿❶
* ❶⓿⓿⓿⓿❶❶⓿⓿❶
* ❶❶❶❶❶❶❶❶❶❶
* ❶❶❶❶❶❶❶❶❶❶
* ❶❶❶❶❶❶❶❶❶❶
* ❶❶❶❶❶❶❶❶❶❶
* ❶❶❶❶❶❶❶❶❶❶
* ❶❶❶❶❶❶❶❶❶❶
*/
public class Main {
//public static Data[] DT= new Data[1000];
public static int north=0;
public static int west=0;
public static int east=0;
public static int south=0;
public static int x=1,y=1;
public static char[][] arr = new char[10][10];
public static Stack st = new Stack();
public static void main(String args[]){
FileReader read = null;
try{
read = new FileReader("E:\\eclipse\\数据结构\\src\\栈原理迷宫游戏\\map");
char c;
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
c=(char) read.read();
if(c=='\r'){
c=(char) read.read();
System.out.println();
c=(char) read.read();
arr[i][j]=c;
System.out.print(c);
}else{
arr[i][j]=c;
System.out.print(c);
}
}
}
System.out.println("asd");
int f0 = 10;
int f1 = 10;
Data dta;
///int x0=0;
//int y0=0;
//每次 一次查找的方向为0,1,2,3；即：东南西北
Data asd = new Data();
if(arr[x][y]=='0'){
asd.x=x;
asd.y=y;
asd.f=0;
st.push(asd);
}
int xx=0,yy=0,xxx=0,yyy=0;
int p = 1;
int i=0;
while(true){
xx=x+1;
yy=y+1;
xxx=x-1;
yyy=y-1;
if(arr[xxx][y]=='2'||arr[xx][y]=='2'||arr[x][yyy]=='2'||arr[x][yy]=='2'){
if(arr[xxx][y]=='2'){
Data b = new Data();
b.x=xxx;
b.y=y;
st.push(b);
}else if(arr[xx][y]=='2'){
Data b = new Data();
b.x=xxx;
b.y=y;
st.push(b);
}else if(arr[x][yyy]=='2'){
Data b = new Data();
b.x=xxx;
b.y=y;
st.push(b);
}else if(arr[x][yy]=='2'){
Data b = new Data();
b.x=xxx;
b.y=y;
st.push(b);
}
System.out.println("--找到出口--");
break;
}
dta=st.look();
f0=dta.f;
if(p == i)
{
st.print();
p++;
if(p==12){
System.out.println("----------");
}
System.out.println("----------");
}
i++;
if(east()){
Data a = new Data();
y=y+1;
a.x=x;
a.y=y;
a.f=0;
arr[x][y]='*';
st.push(a);
}else if(south()){
Data a = new Data();
x=x+1;
a.x=x;
a.y=y;
a.f=1;arr[x][y]='*';
st.push(a);
}else if(west()){
Data a = new Data();
y=y-1;
a.x=x;
a.y=y;
a.f=2;arr[x][y]='*';
st.push(a);
}else if(north()){
Data a = new Data();
x=x-1;
a.x=x;
a.y=y;
a.f=3;arr[x][y]='*';
st.push(a);
}else{
f1=st.look().f;
if(st.look().f==0){
st.pop();
arr[x][y]='3';
dta=st.look();
//dta.f=1;
x=dta.x;
y=dta.y;
f0=dta.f;
}else if(st.look().f==1){
st.pop();
arr[x][y]='3';
dta=st.look();
//dta.f=2;
x=dta.x;
y=dta.y;
f0=dta.f;
}else if(st.look().f==2){
st.pop();
arr[x][y]='3';
dta=st.look();
//dta.f=3;
x=dta.x;
y=dta.y;
f0=dta.f;
}else if(st.look().f==3){
st.pop();
arr[x][y]='3';
dta=st.look();
//sdta.f=0;
x=dta.x;
y=dta.y;
f0=dta.f;
}
}
for(int ii=0;ii<10;ii++){
for(int j=0;j<10;j++){
System.out.print(arr[ii][j]);
}
System.out.println();
}
if(st.isEmpty()){
System.out.println("没找到！！！");
break;
}
}
}catch(IOException e){
e.printStackTrace();
}finally{
if(read != null){
try{
read.close();
}catch(IOException e){
e.printStackTrace();
}
}
}
}
//四个函数，每次仅仅看一下想走的位置上是否能走(为0能走)；并且看一下栈中是否已经走过此位置0
public static boolean east(){ //0
int y0 = y+1;
Data a = new Data();
a.x=x;
a.y=y0;
if(y0>=10){
return false;
}else{
if(arr[x][y0]=='0'&&st.find(a)==false){
return true;
}
}
return false;
}
public static boolean west(){ //2
int y0=y-1;
Data a = new Data();
a.x=x;
a.y=y0;
if(y0<0){
return false;
}else{
if(arr[x][y0]=='0'&&st.find(a)==false){
return true;
}
}
return false;
}
public static boolean south(){ //1
int x0=x+1;
Data a = new Data();
a.x=x0;
a.y=y;
if(x0>=10){
return false;
}else{
if(arr[x0][y]=='0'&&st.find(a)==false){
return true;
}
}
return false;
}
public static boolean north(){ //3
int x0=x-1;
Data a = new Data();
a.x=x0;
a.y=y;
if(x0<0){
return false;
}else{
if(arr[x0][y]=='0'&&st.find(a)==false){
return true;
}
}
return false;
}
public static boolean Success(){
int x0=x;
int y0=y;
if(arr[x0][y0]=='2'){
return true;
}
return false;
}
}
在这里我把pop出栈的坐标标记成了‘3’，把地图弄到了文本文件里，便于修改地图，弄的有点麻烦了，下次使用回朔法做一次.....
