迷宫问题_走迷宫
迷宫问题
import java.util.*;
class pair{
//保存坐标!
public int x;
public int y;
public pair(int x,int y){
this.x = x;
this.y = y;
}
}
public class Main{
static int[][] next = {{-1,0},{1,0},{0,-1},{0,1}};
public static boolean DFS(int[][] array,int row,int col,int curx,int cury,ArrayList<pair> result){
if(curx==row-1&&cury==col-1){
return true;//结束! 已经找到了该路径!
}
for(int i = 0;i<next.length;i++){
int x = curx + next[i][0];
int y = cury + next[i][1];
if(x<0||x>=row||y<0||y>=col){
//越界
continue;
}
if(array[x][y]==0){
//可走!
//保存该位置!
result.add(new pair(x,y));
//标记该位置走过!
array[x][y] = 1;
if(DFS(array,row,col,x,y,result)){
//到达了
return true;
}
//回溯
result.remove(result.size()-1);
array[x][y] = 0;
}
}
//未找到该路径需要回退!
return false;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int row = sc.nextInt();
int col = sc.nextInt();
int[][] array = new int[row][col];
for(int i = 0;i<row;i++){
for(int j = 0;j<col;j++){
array[i][j] = sc.nextInt();
}
}
ArrayList<pair> result = new ArrayList<>();
result.add(new pair(0,0));
DFS(array,row,col,0,0,result);
for(pair cur:result){
System.out.println("("+cur.x+","+cur.y+")");
}
}
}
} 走迷宫
// dfs深度优先搜索
import java.util.*;
public class Main{
static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
public static void dfs(int x, int y, char[][] maze, int[][] map){
for(int i = 0; i < 4; i++){
int xx = x + direction[i][0];
int yy = y + direction[i][1];
if(xx >= 0 && xx < 10 && yy >= 0 && yy < 10
&& maze[xx][yy] == '.' && map[xx][yy] > map[x][y]+1){
map[xx][yy] = map[x][y] + 1;
dfs(xx, yy, maze, map);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
char[][] maze = new char[10][10];
int[][] map = new int[10][10];
for(int i = 0; i < 10; i++){
String str = sc.next();
for(int j = 0; j < 10; j++){
maze[i][j] = str.charAt(j);
map[i][j] = Integer.MAX_VALUE;
}
}
map[0][1] = 0;
dfs(0, 1, maze, map);
System.out.println(map[9][8]);
}
}
} // bfs广度优先搜索
import java.util.*;
public class Main{
static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
static class Node{
int x, y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
char[][] maze = new char[10][10];
int[][] map = new int[10][10];
boolean[][] visited = new boolean[10][10];
for(int i = 0; i < 10; i++){
String str = sc.next();
for(int j = 0; j < 10; j++){
maze[i][j] = str.charAt(j);
if(maze[i][j] == '#'){
visited[i][j] = true;
}
}
}
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(0, 1));
while(!queue.isEmpty()){
Node cur = queue.poll();
for(int i = 0; i < 4; i++){
Node next = new Node(cur.x+direction[i][0], cur.y+direction[i][1]);
if(next.x >= 0 && next.x < 10 && next.y >= 0 && next.y < 10
&& !visited[next.x][next.y]){
queue.offer(next);
map[next.x][next.y] = map[cur.x][cur.y] + 1;
visited[next.x][next.y] = true;
}
}
}
System.out.println(map[9][8]);
}
}
}
//bfs2
// write your code here
import java.util.*;
class pare {
int x;
int y;
int step;
public pare(int x,int y,int step){
this.x = x;
this.y = y;
this.step = step;
}
}
public class Main{
public static int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
char[][] map = new char[10][10];
while(sc.hasNext()){
for(int i = 0;i<10;i++){
String tmp = sc.nextLine();
for(int j = 0;j<10;j++){
map[i][j] = tmp.charAt(j);
}
}
pare start = new pare(0,1,0);
System.out.println(bfs(map,10,10,start));
}
}
public static int bfs(char[][] map,int row,int col,pare start){
//广度优先!
Queue<pare> q = new LinkedList<>();
q.offer(start);
while (!q.isEmpty()){
pare cur = q.poll();
if(cur.x==9&&cur.y==8){
return cur.step;
}
for (int i = 0; i <next.length; i++) {
int x = cur.x + next[i][0];
int y = cur.y + next[i][1];
int step = cur.step + 1;
if(x>=0&&x<row&&y>=0&&y<col&&map[x][y]=='.'){
//标记已经走过!
map[x][y] = '#';
//入队!
q.offer(new pare(x,y,step));
}
}
}
return 0;
}
} #笔试#