首页 > 试题广场 > 迷宫问题
[编程题]迷宫问题

定义一个二维数组N*M(其中2<=N<=10;2<=M<=10),如5 × 5数组下所示: 


int maze[5][5] = {


        0, 1, 0, 0, 0,


        0, 1, 0, 1, 0,


        0, 0, 0, 0, 0,


        0, 1, 1, 1, 0,


        0, 0, 0, 1, 0,


};


它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。

Input

一个N × M的二维数组,表示一个迷宫。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

Output

左上角到右下角的最短路径,格式如样例所示。

Sample Input

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)
 

 

 


输入描述:

输入两个整数,分别表示二位数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。



输出描述:

左上角到右下角的最短路径,格式如样例所示。

示例1

输入

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
用回溯法,给了详细注释~~~~供参考,自以为代码还是比较清晰的
MazeTrack()函数用来递归走迷宫,具体步骤为:
1. 首先将当前点加入路径,并设置为已走
2. 判断当前点是否为出口,是则输出路径,保存结果;跳转到4
3. 依次判断当前点的上、下、左、右四个点是否可走,如果可走则递归走该点
4. 当前点推出路径,设置为可走
#include<iostream>
#include<vector>
using namespace std;

int N, M; //分别代表行和列
vector<vector<int>> maze;//迷宫矩阵
vector<vector<int>> path_temp;//存储当前路径,第一维表示位置
vector<vector<int>> path_best;//存储最佳路径

void MazeTrack(int i, int j)
{
	maze[i][j] = 1;//表示当前节点已走,不可再走
	path_temp.push_back({ i, j });//将当前节点加入到路径中

	if (i == N - 1 && j == M - 1) //判断是否到达终点
		if (path_best.empty() || path_temp.size() < path_best.size())
			path_best = path_temp;

	if (i - 1 >= 0 && maze[i - 1][j] == 0)//探索向上走是否可行
		MazeTrack(i - 1, j);
	if (i + 1 < N && maze[i + 1][j] == 0)//探索向下走是否可行
		MazeTrack(i + 1, j);
	if (j - 1 >= 0 && maze[i][j - 1] == 0)//探索向左走是否可行
		MazeTrack(i, j - 1);
	if (j + 1 < M && maze[i][j + 1] == 0)//探索向右走是否可行
		MazeTrack(i, j + 1);
	maze[i][j] = 0;         //恢复现场,设为未走
	path_temp.pop_back();
}
int main()
{
	while (cin >> N >> M)
	{
		maze = vector<vector<int>>(N, vector<int>(M, 0));
		path_temp.clear();
		path_best.clear();
		for (auto &i : maze)
			for (auto &j : i)
				cin >> j;
		MazeTrack(0, 0);//回溯寻找迷宫最短通路
		for (auto i : path_best)
			cout << '(' << i[0] << ',' << i[1] << ')' << endl;//输出通路
	}
	return 0;
} 


发表于 2017-06-29 21:13:15 回复(15)
import java.util.*;

public class Main {
	
    public static void main(String[] args) {
    	Scanner jin = new Scanner(System.in);
    	while(jin.hasNext()) {
    		int row = jin.nextInt();
    		int col = jin.nextInt();
    		int[][] maze = new int[row][col];
    		for(int i = 0; i < row; i++)
    			for(int j = 0; j < col; j++)
    				maze[i][j] = jin.nextInt();
    		check(maze, 0, 0);//预先探测迷宫一遍,将走不通的路置1
    		System.out.println(mazePath(maze, 0, 0));//正式走迷宫
    	}
    }
    public static int check(int[][] maze, int x, int y) {
        //如果是右下角的出口
    	if(x == maze.length - 1 && y == maze[x].length - 1) return 1;
        //如果当前位置是路
    	if(x < maze.length && y < maze[maze.length - 1].length && maze[x][y] == 0) {
                //如果下一步横竖都是死
    		if(check(maze, x + 1, y) == -1 && check(maze, x, y + 1) == -1) {
                        //将本位置封死
    			maze[x][y] = 1;
    			return -1;
    		}else return 1;
        //如果当前位置不是路
    	}else return -1;
    }
    public static String mazePath(int[][] maze, int x, int y) {
        //如果是右下角的出口,返回坐标
    	if(x == maze.length - 1 && y == maze[x].length - 1) return "(" + x + "," + y + ")";
        //如果当前位置是路,返回坐标并且继续前进
    	if(x < maze.length && y < maze[maze.length - 1].length && maze[x][y] == 0) return "(" + x + "," + y + ")" + "\n" + mazePath(maze, x + 1, y) + mazePath(maze, x, y + 1);
        //如果当前位置不是路,什么也不做
    	else return "";
    }
}

发表于 2016-08-25 03:09:15 回复(7)
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
 
int main(){
    int N, M;
    while(cin >> N >> M){
        int **a =new int*[N];
        for(int i =0; i<N; i++){
            a[i] =new int[M];
        }
        for(int i =0; i<N; i++){
            for(int j =0; j<M; j++){
                cin >> a[i][j];
            }
        }
        int dir[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };//点的四个方向:下,右,上,左
        int visit[11][11] = {0}; //判定该点是否走过
        bool flag =0; //是否走完
        stack<pair<int,int>> stk;
        stk.push(make_pair(0,0));
        stk.push(make_pair(0,0));
        visit[0][0] =1;
        while(!flag){   //深度优先搜索思想,往该点四个方向探查,若有则从这点继续探寻,若没有则回溯到上一个点
            pair<int,int> p = stk.top();   //回退路径的点
            stk.pop();
            int i = p.first, j= p.second;
            for(int k =0; k <4;k++){  //对四个方向进行探查
                int dx = i + dir[k][0];
                int dy = j + dir[k][1];
                if(dx == N-1&&dy == M-1){ //到达终点
                    stk.push(make_pair(N-1, M-1));
                    flag =true;
                    break;
                }
                if(dx>=0&& dx<=N-1&& dy>=0&& dy<=M-1&& a[dx][dy] ==0&& visit[dx][dy] ==0){  //未被访问过且有路径
                    stk.push(make_pair(dx, dy));
                    visit[dx][dy] =1;
                    i = dx;     //从该点继续探查
                    j = dy;
                    k=-1;
                }
            }
        }
        stack<pair<int,int>> outputStk;  //把栈的先后顺序换一下输出
        while(!stk.empty()){
            outputStk.push(stk.top());
            stk.pop();
        }
        while(!outputStk.empty()){
            pair<int,int> p = outputStk.top();
            outputStk.pop();
            cout <<"("<<p.first<<","<<p.second<<")"<< endl;
        }
    }
    return0;
}
编辑于 2016-04-04 17:08:16 回复(3)
深度优先搜索: 
 之前我们求最短路径用的广度优先搜索,这个题看似是最短路径问题,其实不是,因为题目上说了只有一条通路,而且还要输出这个路径,那么深度优先搜索比较合适,当然广度优先搜索也可以。深度优先搜索的思想是沿着一个方向搜到底,如果行不通,则返回来试其他的路径。就一直这样直到找到一条通路输出就可以了。其实这个思想网上一大堆,但是具体怎么实现呢?下面我贴上自己的代码,代码中会有详细的注释,希望会帮到大家: import java.util.Stack;
public class Main {
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
         while (sc.hasNext()) {
             int m = sc.nextInt();
             int n = sc.nextInt();
             int[][] map = new int[m][n];//定义一个Map矩阵,用来保存地图
             for (int i = 0; i < m; i++) {
                 for (int j = 0; j < n; j++) {
                     map[i][j] = sc.nextInt();//输入地图
                 }
             }
             int[][] dir = {{1, 0}, {0, 1}};//定义两个方向横着走或者竖着走(题目中说只走这两个方向,当前也可以定义多个方向)
             Stack<Node> stack = new Stack<Node>();//定义一个栈,保存路径
             int[][] visited = new int[m][n];//标记是否被访问,这个要和Map大小对应
             Node start = new Node(0, 0);//定义起始位置
             Node end = new Node(m - 1, n - 1);//定义目的位置
             visited[start.x][start.y] = 1;//将起始点标记为访问
             stack.push(start);//将起始点加入队列
             while (!stack.isEmpty()) {//如果对了为空了还没有找到解,说明就没有通路,当然本题不存在无解,题目上说了一定存在一个通路。
                 boolean flag = false;//标记是否找了一个方向
                 Node pek = stack.peek();//获取栈顶元素,注意不需要出栈
                 if (pek.x == end.x && pek.y == end.y) {//如果到达目的地则跳出循环
                     break;
                 } else {
                     for (int i = 0; i < 2; i++) {//循环两个方向
                         Node nbr = new Node(pek.x + dir[i][0], pek.y + dir[i][1]);//找到当前位置的邻居位置坐标并判断是否合法
                         if (nbr.x >= 0 && nbr.x < m && nbr.y >= 0 && nbr.y < n && map[nbr.x][nbr.y] == 0 && visited[nbr.x][nbr.y] == 0) {//判断邻居节点是否合法
                             stack.push(nbr);//合法将邻居位置加入栈
                             visited[nbr.x][nbr.y] = 1;//并标记该节点已经访问
                             flag = true;//找到了一个方向
                             break;//找到了就停止循环,顺着这个方向一直搜索
                         }
                     }
                     if (flag) {//找到了方向,就不用执行下面的出栈,沿着这个方向一直搜下去
                         continue;
                     }
                     stack.pop();//如果两个方向都不能通过,则出栈。
                 }
             }
             Stack<Node> stkRev = new Stack<Node>();//将路径反过来,因为栈中输出的路径是反的
             while (!stack.isEmpty()) {
                 stkRev.push(stack.pop());
             }
             while (!stkRev.isEmpty()) {
                  System.out.println("(" + stkRev.peek().x + "," + stkRev.peek().y + ")");
                 stkRev.pop();
             }
         }
    }
}
class Node{
    int x;
    int y;
    Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}
2.广度优先搜索:
    广搜的套路就是利用一个队列,每次将当前点的邻居节点加入队列,然后出队,在将当前点加入队列,一直讲所有路径搜索完毕,直到队列为空停止。同时还需要一个数组去保存该节点是否访问,做个标记。但是怎样输出路径呢,我采取的办法是每次我们需要保存一下当前节点的前驱节点,可以这样设计一个类保存当前坐标和前驱坐标:class Node{
    int x;
    int y;
    int prex;
    int prey;
}
下面附上代码:import java.util.*;
/**
 * Created by Administrator on 2015/12/21.
 */
public class BFS {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            int m=sc.nextInt();
            int n=sc.nextInt();
            int[][] map = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            int[][] dir = {{1, 0}, {0, 1}};
            int[][] visited=new int[m][n];
            Node start=new Node(0,0);
            Node end=new Node(m-1,n-1);
            Queue<Node> queue=new LinkedList<Node>();
            ArrayList<Node> arrayList=new ArrayList<Node>();//用来保存每一个出队列的节点
            queue.offer(start);
            while (!queue.isEmpty()){
                Node local=queue.remove();
                arrayList.add(local);
                for (int i=0;i<2;i++){
                    Node nbr=new Node(local.x+dir[i][0],local.y+dir[i][1]);
                    if(nbr.x>=0&&nbr.x<m&&nbr.y>=0&&nbr.y<n&&map[nbr.x][nbr.y]==0&&visited[nbr.x][nbr.y]==0){
                        visited[nbr.x][nbr.y]=1;
                        queue.offer(nbr);
                        nbr.prex=local.x;//保存前驱节点
                        nbr.prey=local.y;//保存前驱节点
                    }
                }
            }
            Stack<Integer> stack=new Stack<Integer>();
            int  px=arrayList.get(arrayList.size()-1).prex;//获得目的节点的前驱节点
            int  py=arrayList.get(arrayList.size()-1).prey;
            stack.push(arrayList.size()-1);//将目的节点在arrayList中的位置记录下来,便于输出
            while (true){
                if(px==0&&py==0){//找到起始节点就停止
                    break;
                }
                for(int i=0;i<arrayList.size();i++){//循环找出每一个节点的前驱,找到就跳出当前循环
                    if(arrayList.get(i).x==px&&arrayList.get(i).y==py){
                        px=arrayList.get(i).prex;
                        py=arrayList.get(i).prey;
                        stack.push(i);//保存节点在arrayList中的位置
                        break;
                    }
                }
            }
            System.out.println("(0,0)");
            while (!stack.isEmpty()){
                System.out.println("("+arrayList.get(stack.peek()).x+","+arrayList.get(stack.peek()).y+")");
                stack.pop();
            }

        }
    }
}

class Node{
    int x;
    int y;
    int prex;//保存前驱节点位置
    int prey;
    Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}

发表于 2016-01-05 09:52:03 回复(13)
迷宫一般用回溯法,即用栈或递归,下面用递归解题
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
bool HasPathCore(vector<vector<int>> data, int row, int col, vector<vector<bool>> &visited, vector<vector<int>> &res){
	bool hasPath = false;
	int rows = data.size();
	int cols = data[0].size();
	if (row == rows - 1 && col == cols - 1){
		vector<int> cur(2);
		cur[0] = rows - 1, cur[1] = cols - 1;
		res.push_back(cur);
		return true;
	}
	if (row >= 0 && row<rows && col >= 0 && col<cols && data[row][col] == 0 && visited[row][col] == false){
		visited[row][col] = true;
		vector<int> cur(2);
		cur[0] = row, cur[1] = col;
		res.push_back(cur);
		hasPath = HasPathCore(data, row, col - 1,  visited, res) ||
			HasPathCore(data, row - 1, col,  visited, res) ||
			HasPathCore(data, row + 1, col,  visited, res) ||
			HasPathCore(data, row, col + 1, visited, res);
		if (!hasPath){
			visited[row][col] = false;
		}
	}
	return hasPath;
}
int main(){
	int n, m;
	while (cin >> n >> m){
		vector<vector<int>> data;
		vector<vector<bool>> visited;
		for (int i = 0; i<n; ++i){
			vector<int> row;
			vector<bool> row2;
			for (int j = 0; j<m; ++j){
				int temp;
				cin >> temp;
				row.push_back(temp);
				row2.push_back(false);
			}
			data.push_back(row);
			visited.push_back(row2);
		}
		vector<vector<int>> res;
		int pathlength = 0;
	      if (HasPathCore(data, 0, 0, visited, res)) {
			for (int i = 0; i < res.size(); ++i){
				vector<int> cur = res[i];
				cout << '(' << cur[0] << ',' << cur[1] << ')' << endl;
			}
        }
	}
	return 0;
}

编辑于 2016-09-12 21:57:32 回复(5)
//非深度优先遍历求解,一种回溯的方法
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct A{
    int x;
    int y;
};
A W[4]={{-1,0},{1,0},{0,-1},{0,1}};
bool is(vector<vector<int> > vec, struct A a,struct A b,int M, int N, int num){
    if(a.x+b.x>=0&&a.x+b.x<M&&a.y+b.y>=0&&a.y+b.y<N&&vec[a.x+b.x][a.y+b.y]==num)
        return true;
    else 
    	return false;
}
int main(){
    int M,N;
    while(cin>>M>>N){
        vector<vector<int> > vec(M,vector<int>(N));
        for(int i=0;i<M;i++)
            for(int j=0;j<N;j++)
            	cin>>vec[i][j];
        queue<A> Q;
        A a={0,0};
        vec[0][0]=2;
        Q.push(a);
        while(!Q.empty()){
            a=Q.front();
            Q.pop();
            int flag=0;
            for(int i=0;i<4;i++)
            	if(is(vec,a,W[i],M,N,0)){
                	vec[a.x+W[i].x][a.y+W[i].y]=vec[a.x][a.y]+1;
                	if(a.x+W[i].x==M&&a.y+W[i].y==N){
                        flag=1;
                        break;
                    }    
		    A temp={a.x+W[i].x,a.y+W[i].y};
                    Q.push(temp);           	
            }
            if(flag)
                break;
        }
        a.x=M-1;a.y=N-1;
        vector<A> v;
        v.push_back(a);
        while(!(a.x==0&&a.y==0)){
            for(int i=0;i<4;i++)
                if(is(vec,a,W[i],M,N,vec[a.x][a.y]-1)){
                	a.x=a.x+W[i].x;
					a.y=a.y+W[i].y;
                	v.push_back(a);
                	break;
            	}
        }
        for(int i=v.size()-1;i>=0;i--)
            cout<<"("<<v[i].x<<","<<v[i].y<<")"<<endl;
    }
    return 0;
}

编辑于 2016-08-01 20:19:29 回复(0)
/*
因为虽然最短路径只有一条但是通路不只一条,所以得用广度优先搜索的思想
因为广度优先搜索的经典写法while(q.size()){}记录最佳路径是个难点,故不用经典写法
本程序使用的是递推,虽然形式上像递归————自定义函数track在定义中调用了自己————但是没有回归操作,仅仅是递推而已。
具体思路讲解:
1. 递推过程中某点可走的三个条件:(a)不越界;(b)不碰壁;(c)没走过。
由于本程序将走过的点都设置成-1,而墙壁都是1,故maze[x][y]==0即同时满足条件(b)和(c)
2. 之所以上下左右四个可能方向都要判定能否走,即是广度优先搜索的思想。之所以将走过的点的迷宫数组值设为-1以及在某点是否可走的判定条件中添加“未走过”这一条件,是因为:“第二次及以上到达某点后最终得出的通路肯定不是最短通路”,这一真命题的逆否命题即等效说法为,“在从入口沿着最短通路到达出口的这一过程中走到各点时均为第一次到达该点”。故满足每次到达的点不越界不碰壁且未走过则第一次到达出口的路径即为最短路径。那么如何保证第一次到达出口后即终止track函数的操作呢?在将track函数输入点的坐标标记为走过然后存储后即判断该点是否为出口,是则return;终止track函数。

程序写法讲解:
1. 由于此程序的主函数需要调用自定义函数track,track会用到一些主函数中出现的变量(比如迷宫尺寸n和m,迷宫的存储数组maze,最短路径的存储向量path),而这些变量并不是自定义函数的关键输入参数,一并作为track的输入参数会时track函数显得臃肿,使用起来也不方便。故将这些变量作为全局变量放在主函数和自定义函数的前面进行声明。
2. 由于track函数最终要返回的就是vector<loc> path,将最短路径存储向量vector<loc> path作为全局变量进行声明后,track函数只需要输入参数不需要返回参数了,即void track(int x,int y){...return;...},但是主函数中每次输入新的用例后需要对path进行清空,防止上一用例的结果影响到这次用例的测试。
3. 坐标类型的定义用到pair,即typedef pair<int,int> loc;
4. (a)用pair定义的loc类型的变量的定义及初始化:loc p(0,0);与一般类型的定义及初始化的区别在于p和(0,0)间不需要等号。
(b)由用pair定义的loc类型的变量取出横(纵)坐标:loc p;p.first为横坐标,p.second为纵坐标。
5. 二维向量的定义以及尺寸的确定:vector<vector<int>> maze(n,vector<int>(m));//定义了一个尺寸为n*m的二维整型向量maze
6. 二维向量定义的同时全部初始化为同一值可用vector<vector<int>> 二维向量名(n,vector<int>(m,要初始化的值));
*/
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int,int> loc;
int n, m; //迷宫的尺寸n*m的声明
vector<vector<int>> maze(n,vector<int>(m));//迷宫存储数组的声明
vector<loc> path;//最短路径存储向量的声明

void track(int x, int y) //找出从迷宫中某点loc(x,y)走到出口的最短路径,并存储到全局向量vector<loc> path中
{
    maze[x][y] = -1;//表示当前节点已走,不可再走
    path.push_back(loc(x,y));//将当前节点的位置加入到最短路径中
 
    if (x==n-1 && y==m-1) //判断是否到达终点,若到达即为第一次到达,此时path中存储的路径即为最短路径,return;终止track函数的运行
        return ;
    
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};//分别对应下右上左四个前进方向的行列位置变化
    for(int i=0;i<4;i++)
    {
        if(   x+dx[i]>=0 && x+dx[i]<n && y+dy[i]>=0 && y+dy[i]<m //不越界
           && maze[x+dx[i]][y+dy[i]]==0 //不碰墙且未走过
          )
            track(x+dx[i], y+dy[i]); //问题转化为找出从loc(x+dx[i], y+dy[i])走到出口的最短路径,并存储到全局向量vector<loc> path中
    }
}

int main()
{
    while (cin >> n >> m)
    {
        maze = vector<vector<int>>(n, vector<int>(m));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>maze[i][j];
        path.clear();//因为path为全局向量,所以还残留着上一个用例的最短路径,需清空
        track(0,0); 
        for(int i=0;i<path.size();i++)
            cout << '(' << path[i].first << ',' << path[i].second << ')' << endl;
    }
    return 0;
}

编辑于 2018-07-08 00:46:31 回复(0)
#include <iostream>
#include <algorithm>

using namespace std;

int N,M;
vector<vector<int>> maze, mbest, mtmp;

//四个方向递归查找
void mazeTrack(int x, int y)
{
    maze[x][y] = 1;    //已走标记
    mtmp.push_back({x,y});
    
    if(x==N-1 && y==M-1)    //已走通
        if(mtmp.size()<mbest.size() || mbest.empty()) {
            mbest = mtmp;
            goto _END;    //到达终点不再继续该通道
        }
    
    if(x>0 && maze[x-1][y]==0)    //向上
        mazeTrack(x-1,y);
    if(x<N-1 && maze[x+1][y]==0)    //向下
        mazeTrack(x+1,y);
    if(y>0 && maze[x][y-1]==0)    //向左
        mazeTrack(x,y-1);
    if(y<M-1 && maze[x][y+1]==0)    //向右
        mazeTrack(x,y+1);

_END:
    //该条通道不可继续,回到上一层走上一个点的其他分支
    maze[x][y] = 0;    //恢复标记,因只有该点可走时才会走所以原本为0
    mtmp.pop_back();
}

int main()
{
    while(cin>>N>>M) {
        //输入存储
        maze = vector<vector<int>>(N, vector<int>(M,0));
            
        for(auto &i:maze)
            for(auto &j:i)
                cin>>j;
        
        mazeTrack(0, 0);
        for(auto x:mbest)
            cout<<"("<<x[0]<<","<<x[1]<<")"<<endl;
        
        maze.clear();
        mbest.clear();
        mtmp.clear();
    }
}

发表于 2019-08-10 12:29:19 回复(0)
try:
    while True:
        row,col = map(int,input().split())
        maze = []
        for i in range(row):
            maze.append(list(map(lambda x:-x,map(int,input().split()))))
        queue = [[0,0]]
        maze[0][0] = 1
        while queue:
            x,y = queue.pop(0)
            if x == row-1 and y == col-1:
                break
            if x+1 < row and maze[x+1][y] == 0:
                maze[x+1][y] = maze[x][y]+1
                queue.append([x+1,y])
            if y+1 < col and maze[x][y+1] == 0:
                maze[x][y+1] = maze[x][y]+1
                queue.append([x,y+1])
            if x-1 >= 0 and maze[x-1][y] == 0:
                maze[x-1][y] = maze[x][y]+1
                queue.append([x-1,y])
            if y-1 >= 0 and maze[x][y-1] == 0:
                maze[x][y-1] = maze[x][y]+1
                queue.append([x,y-1])
        result = [[row-1,col-1]]
        for i in range(maze[-1][-1]-1,0,-1):
            tempRow = result[0][0]
            tempCol = result[0][1]
            if tempRow-1>=0 and maze[tempRow-1][tempCol] == i:
                result.insert(0,[tempRow-1,tempCol])
            elif tempCol-1>=0 and maze[tempRow][tempCol-1] == i:
                result.insert(0,[tempRow,tempCol-1])
            elif tempRow+1<row and maze[tempRow+1][tempCol] == i:
                result.insert(0,[tempRow+1,tempCol])
            elif tempCol+1<col and maze[tempRow][tempCol+1] == i:
                result.insert(0,[tempRow,tempCol+1])
        for i in result:
            print('(%d,%d)'%(i[0],i[1]))
except Exception:
    pass
编辑于 2018-11-06 20:09:53 回复(1)
#coding=utf-8
while True:
    try:
        m,n=map(int,raw_input().split())
        a=[]
        for i in range(m):
            a.append(map(int,raw_input().split()))
        v=[[0 for i in range(n)]for j in range(m)]#visit
        d=[[0,1],[0,-1],[1,0],[-1,0]]#direction
        c=[1,1,3,0]#cost
        s=[]#step
        s.append([0,0])#begin at (0,0)
        v[0][0]=1#(0,0)has been visited
        i,j=s[-1]#init position
        k=0
        while k<4:#BFS
            x=i+d[k][0]
            y=j+d[k][1]
            if x>=0 and y>=0 and x<m and y<n and a[x][y]==0 and v[x][y]==0:
                s.append([x,y])
                v[x][y]=1
                i=x
                j=y
                k=-1
            if x==m-1 and y==n-1:
                break
            if k==3:
                s.pop()
            k+=1
        for k in s:
            print '(%d,%d)'%(k[0],k[1])
    except:
        break
编辑于 2017-08-19 22:18:14 回复(0)
//深度优先+回溯法  与  广度优先+前驱节点
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] maz = new int[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    maz[i][j] = sc.nextInt();
                }
            }
            int[][] flag = new int[n][m];
            //bfs(maz,n,m,flag); 广度优先
            ArrayList<Stack<Node>> list = new ArrayList<Stack<Node>>();
            Stack<Node> stack = new Stack<Node>();
            flag[0][0] =2;
            stack.push(new Node(0,0));
            dfs(0,0,maz,stack,list,flag); //深度优先
            dfsOut(list);
        }
    }
    
    public static void dfs(int i,int j,int[][] maz,Stack<Node> stack,ArrayList<Stack<Node>> list,int[][] flag){
    	if(i == maz.length-1 && j == maz[0].length-1){
    		Stack<Node> stack1 = new Stack<Node>();
    		ArrayList<Node> alist = new ArrayList<Node>();
    		while(!stack.isEmpty()){
    			Node node1 = stack.pop();
    			stack1.push(node1);             //复制栈
    			alist.add(node1);
    		}
    		for(int k=alist.size()-1;k>0;k--){  //不要最后一个
    			stack.push(alist.get(k));
    		}
    		list.add(stack1);
        	flag[i][j] = 0;                    //最后一个清0
    		return;
    	}
    	if(i+1<maz.length && maz[i+1][j]==0 && flag[i+1][j]==0){
    		stack.push(new Node(i+1,j));
    		flag[i+1][j] = 2;
    		dfs(i+1,j,maz,stack,list,flag);
    	}
    	if(i-1>=0 && maz[i-1][j]==0 && flag[i-1][j]==0){
    		stack.push(new Node(i-1,j));
    		flag[i-1][j] = 2;
    		dfs(i-1,j,maz,stack,list,flag);
    	}
    	if(j+1<maz[0].length && maz[i][j+1]==0 &&  flag[i][j+1]==0){
    		stack.push(new Node(i,j+1));
    		flag[i][j+1] = 2;
    		dfs(i,j+1,maz,stack,list,flag);
    	}
    	if(j-1>=0 && maz[i][j-1]==0 && flag[i][j-1]==0){
    		stack.push(new Node(i,j-1));
    		flag[i][j-1] = 2;
    		dfs(i,j-1,maz,stack,list,flag);
    	}
    	
    	Node top = stack.pop();
    	flag[top.x][top.y] = 0;
    }
    
    public static void dfsOut(ArrayList<Stack<Node>> list){
        int minSize = 10000, minIndex=-1;
        for(int i=0;i<list.size(); i++){
        	if(list.get(i).size() < minSi敏感词Index = i;
        		minSize = list.get(i).size();
        	}
        }
        Stack<Node> s = list.get(minIndex);
        while(!s.isEmpty()){
            Node node = s.pop();
            System.out.println("(" + node.x + "," + node.y + ")");
        }
    }
    
    public static void bfs(int[][] maz, int n, int m, int[][] flag){
        Node node0 = new Node(0,0);
        Queue<Node> queue = new LinkedList<Node>();
        ArrayList<Node> list = new ArrayList<Node>();
        queue.offer(node0);
        flag[0][0] =1;
        while(!queue.isEmpty()){
            Node now = queue.poll();
            list.add(now);
            if(now.x == n-1 && now.y == m-1){
                break;
            }else{
                if(now.x+1<n && maz[now.x+1][now.y]==0 && flag[now.x+1][now.y]==0){//下
                    Node right = new Node(now.x+1, now.y);
                    right.prex = now.x;
                    right.prey = now.y;
                    flag[now.x+1][now.y]=1;
                    queue.offer(right);
                }
                if(now.y+1<m && maz[now.x][now.y+1]==0 && flag[now.x][now.y+1]==0){//右
                    Node right = new Node(now.x, now.y+1);
                    right.prex = now.x;
                    right.prey = now.y;
                    flag[now.x][now.y+1] =1;
                    queue.offer(right);
                }
                if(now.x-1>=0 && maz[now.x-1][now.y]==0 && flag[now.x-1][now.y]==0){//上
                    Node right = new Node(now.x-1, now.y);
                    right.prex = now.x;
                    right.prey = now.y;
                    flag[now.x-1][now.y]=1;
                    queue.offer(right);
                }
                if(now.y-1>=0 && maz[now.x][now.y-1]==0 && flag[now.x][now.y-1]==0){//左
                    Node right = new Node(now.x, now.y-1);
                    right.prex = now.x;
                    right.prey = now.y;
                    flag[now.x][now.y-1]=1;
                    queue.offer(right);
                }
            }
        }
        
        Stack<Node> s = new Stack<Node>();
        for(int i=list.size()-1; i>=0; i--){
            Node node = list.get(i);
            if(node.x == n-1 && node.y == m-1){
                s.push(node);
                n = node.prex + 1;
                m = node.prey + 1;
            }
        }
        while(!s.isEmpty()){
            Node node = s.pop();
            System.out.println("(" + node.x + "," + node.y + ")");
        }
    }
    
    static class Node{
        int x;
        int y;
        int prex;
        int prey;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

编辑于 2016-10-07 20:30:40 回复(1)
import java.util.*;
import java.math.*;

public class Main{
    
    public static void fun(int[][] map,int m,int n){
    	int[][] visit = new int[m][n];
    	int[][] dir = {{1, 0}, {0, 1}};
    	
    	int max=0;
    	Stack<Node> queue = new Stack<Node>();
    	
    	Stack<Node> st = new Stack<Node>(); 
    	Node in = new Node(0,0);
    	st.push(in);
    	while(st.size()>0){
    		Node top = st.peek();
    		if(top.x==m-1&&top.y==n-1){
    			//记录一条路径
    			if(max<st.size()){
    				max=st.size();
    				queue.clear();
    				Queue<Node> temp = new LinkedList<Node>();
    				while(st.size()>0){
    					temp.offer(st.peek());
    					queue.push(st.pop());
    				}
    				while(temp.size()>0){
    					st.push(temp.poll());
    				}
    			}
    			st.pop();
    		}
    		else{
    			Node n1 = new Node(top.x+dir[0][0],top.y+dir[0][1]);
    			Node n2 = new Node(top.x+dir[1][0],top.y+dir[1][1]);
    			boolean tag=false;
    			if(n1.x<m&&n1.y<n&&map[n1.x][n1.y]==0&&visit[n1.x][n1.y]!=1){
    				st.push(n1);
    				visit[n1.x][n1.y]=1;
    				tag=true;
    			}
    			if(n2.x<m&&n2.y<n&&map[n2.x][n2.y]==0&&visit[n2.x][n2.y]!=1&&tag==false){
    				st.push(n2);
    				visit[n2.x][n2.y]=1;
    				tag=true;
    			}
    			if(tag==false){
    				st.pop();
    			}
    		}
    	}
    	
    	while(queue.size()>0){
    		Node top = queue.pop();
    		System.out.println("("+top.x+","+top.y+")");
    	}
    	
    }   
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int M = sc.nextInt();
            int N = sc.nextInt();
            int map[][] = new int[M][N];
            for(int i=0;i<M;i++){
            	for(int j=0;j<N;j++){
            		map[i][j] = sc.nextInt();
            	}
            }
            Main m = new Main();
            m.fun(map,M,N);
        }
    }
    
    public static class Node{
        int x;
        int y;
        Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
}

发表于 2016-08-18 17:01:30 回复(0)
深度优先搜索,最短路径得到更新时注意保存。
/* @Date    : 2016-08-13 20:06:37 */
/* @Author  : JieJ (jiej1992@163.com) */

#include <iostream>
#include <vector>
#include <climits>
#include <sstream>

using namespace std;

void dfs(vector<string> &cur_path, vector<string> &final_path, int maze[][10],
int visited[][10], int x, int y, int n, int m, int &min_path_len, stringstream &ss){
    if(visited[x][y] || maze[x][y] == 1 || x<0 || x>n-1 || y<0 || y>m-1){
        return;
    }
    visited[x][y] = 1;
    ss.str("");
    ss << x << y;
	string pos = ss.str();
    cur_path.push_back(pos);

    if(x == n-1 && y == m-1 && maze[x][y] == 0){
        // 找到一条路径,根据路径长度决定是否保存该路径
        if(cur_path.size()-1 < min_path_len){
            final_path = cur_path;  // 复制路径
            min_path_len = cur_path.size()-1;
            // cout << "find a shorter path, min_path_len change to:" << min_path_len << endl;
        }
        // else{
        //     cout << "find a shorter path, min_path_len no change" << endl;
        // }
    }
    else{
        dfs(cur_path, final_path, maze, visited, x+1, y, n, m, min_path_len, ss);
        dfs(cur_path, final_path, maze, visited, x-1, y, n, m, min_path_len, ss);
        dfs(cur_path, final_path, maze, visited, x, y+1, n, m, min_path_len, ss);
        dfs(cur_path, final_path, maze, visited, x, y-1, n, m, min_path_len, ss);
    }

    visited[x][y] = 0;
    cur_path.pop_back();
}

void print_path(vector<string> &final_path){
    for(int i=0; i<final_path.size(); ++i){
        cout << "(" << final_path[i][0] << "," << final_path[i][1] << ")" << endl;
    }
}

int main(){
    int n, m;

    int maze[10][10];
    int visited[10][10];
    int i, j;
    while(cin >> n >> m){
        for(i=0; i<n; ++i){
            for(j=0; j<m; ++j){
                cin >> maze[i][j];
                visited[i][j] = 0;
            }
        }

        vector<string> cur_path;
        vector<string> final_path;
        int x_index = 0;
        int y_index = 0;
        int min_path_len = INT_MAX;
        stringstream ss;

        dfs(cur_path, final_path, maze, visited, x_index,
        y_index, n, m, min_path_len, ss);

        print_path(final_path);
    }


    return 0;
} 


发表于 2016-08-13 21:11:16 回复(0)
#include<iostream>
#include<vector>
#include<stack>
#include<map>
using namespace std;
int main(){
    int n,m;
    while(cin>>n>>m){
        vector<vector<int> > array(n,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                cin>>array[i][j];
        }
        stack<int> colum;
        stack<int> row;
        colum.push(0);
        row.push(0);
        vector<vector<int> > visited(n,vector<int>(m,0));
        visited[0][0]=1;
        while(!(colum.top()==n-1&&row.top()==m-1)){
         int x=colum.top();
         int y=row.top();
         int flag=0;
         if(y+1<m&&array[x][y+1]!=1&&visited[x][y+1]==0&&flag==0){//左
         colum.push(x);
         row.push(y+1);
         visited[x][y+1]=1;
         flag=1;
}
if(x+1<n&&array[x+1][y]!=1&&visited[x+1][y]==0&&flag==0){//下
colum.push(x+1);
         row.push(y);
         visited[x+1][y]=1;
         flag=1;
}
if(x-1>=0&&array[x-1][y]!=1&&visited[x-1][y]==0&&flag==0){//右
         colum.push(x-1);
         row.push(y);
         visited[x-1][y]=1;
         flag=1;
        
}
if(y-1>=0&&array[x][y-1]!=1&&visited[x][y-1]==0&&flag==0){//上
             colum.push(x);
         row.push(y-1);
         visited[x][y-1]=1;
         flag=1;
}
if(!flag){//
colum.pop();
row.pop();
}
if(colum.empty()){
break;
} 
        
}
vector<int> xpos;
vector<int> ypos;
while(!colum.empty()){
xpos.push_back(colum.top());
ypos.push_back(row.top());
colum.pop();
row.pop();
}
for(int i=xpos.size()-1;i>=0;i--){
cout<<'('<<xpos[i]<<','<<ypos[i]<<')'<<endl;
}
        
    }
return 0;
}

编辑于 2016-09-27 21:47:24 回复(3)
//基于剑指offer获取思路,采用回溯法进行解答
#include<iostream> #include<vector>
using namespace std; bool HasPathCore(vector<vector<int>>& maze,int row,int col,vector<vector<bool>> &visit,vector<vector<int>>&res) {     bool hasPath=false;     int rows=maze.size();     int cols=maze[0].size();     //递归的终止条件     if(row==rows-1 && col==cols-1)     {         vector<int> cur;         cur.push_back(row);         cur.push_back(col);         res.push_back(cur);         return true;     }     if(row>=0 && row<rows && col>=0 && col<cols && maze[row][col]==0 && visit[row][col]==false)     {         visit[row][col]=true;                 vector<int> cur;         cur.push_back(row);         cur.push_back(col);         res.push_back(cur);                 hasPath=HasPathCore(maze,row,col-1,visit,res)||             HasPathCore(maze,row-1,col,visit,res)||             HasPathCore(maze,row,col+1,visit,res)||             HasPathCore(maze,row+1,col,visit,res);                 if(!hasPath)             visit[row][col]=false;     }     return hasPath; }
int main() {     int N,M;     while(cin>>N>>M)     {         vector<vector<int>> maze(N,vector<int>(M,0));         vector<vector<bool>> visit(N,vector<bool>(M,false));         for(int i=0;i<N;i++)         {             for(int j=0;j<M;j++)             {                 cin>>maze[i][j];             }         }                 vector<vector<int>> res;                 if(HasPathCore(maze,0,0,visit,res))         {             for(int i=0;i<res.size();i++)             {                 cout<<"("<<res[i][0]<<','<<res[i][1]<<')'<<endl;             }         }     }     return 0; }

发表于 2019-07-31 22:00:31 回复(0)
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int,int> state_t;
typedef pair<int, int> state_t;
void mazeTrack(vector<vector<int>>& maze, int i, int j, int M, int N, vector<state_t>& path_temp, vector<state_t>& path_best){
    maze[i][j] = 1;
    path_temp.push_back({ i, j });
    if (i == M - 1 && j == N - 1){//递归终止条件==》到达终点
        if (path_best.empty() || path_best.size() > path_temp.size())
            path_best = path_temp;        
    }
    if (i - 1 >= 0 && maze[i - 1][j] == 0) mazeTrack(maze, i - 1, j, M, N, path_temp, path_best);//上
    if (i + 1 < M  && maze[i + 1][j] == 0) mazeTrack(maze, i + 1, j, M, N, path_temp, path_best);//下
    if (j - 1 >= 0 && maze[i][j-1] == 0) mazeTrack(maze, i, j-1, M, N, path_temp, path_best);//左
    if (j + 1 < N && maze[i][j+1] == 0) mazeTrack(maze, i, j+1, M, N, path_temp, path_best);//右
    maze[i][j] = 0;//恢复现场,设为未定
    path_temp.pop_back();
}
int main(){
    
    int m, n;
    
    while (cin >> m >> n){
        vector<vector<int>> maze(m, vector<int>(n,0));
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                cin >> maze[i][j];
            }
        }
        vector<state_t> path_temp;
        vector<state_t> path_best;
        mazeTrack(maze, 0, 0, m, n, path_temp, path_best);
        for (auto i : path_best){
            cout << '(' << i.first << ',' << i.second << ')' << endl;
        }
    }
    system("pause");
    return 0;
}

发表于 2019-07-16 21:19:27 回复(0)

标准的python回溯法

 def go_next(tu, node, result, m, n):
    if not (0<=node[0]<m and 0<=node[1]<n):
        return False
    if tu[node[0]][node[1]] == 1:
        return False
    elif node in result[:-1]:
        return False
    else:
        return True
def add_ans(ans, result):
    if len(ans)>= len(result) or len(ans) == 0:
        return copy.deepcopy(result)
    else:
        return ans

while True:
    try:
        m,n = map(int,raw_input().split())
        tu = []
        for i in range(m):
            tu.append(map(int, raw_input().split()))
        ans = []
        def go(result):
            global ans
            if result[-1] == (m-1,n-1):
                ans = add_ans(ans,result)
            else:
                for i in [(0,1),(1,0),(-1,0),(0,-1)]:
                    now = (result[-1][0]+i[0], result[-1][1]+i[1])
                    if go_next(tu, now, result, m, n):
                        result.append(now)
                        go(result)
            if len(result):
                result.pop()
        go([(0,0)])
        for i in ans:
            print ('(%d,%d)' % (i[0], i[1]))
    except:
        raise
发表于 2019-07-14 13:33:32 回复(0)

采用递归思路😎

import java.util.Scanner;
import java.util.Stack;

class Point{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main{
    private static int rows;
    private static int cols;
    private static Stack<Point> tempPath = new Stack<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            rows = sc.nextInt();
            cols = sc.nextInt();
            int[][] map = new int[rows][cols];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            mazeTrack(map, 0, 0);
        }
    }

    public static void mazeTrack(int[][] map, int x, int y){
        Point p = new Point(x, y);
        tempPath.push(p);
        map[x][y] = 1;
        if (x == rows - 1 && y == cols - 1) {
            for (Point point : tempPath){
                System.out.println("(" + point.x + "," + point.y + ")");
            }
        }
        if (x + 1 < rows && map[x + 1][y] == 0) { //下
            mazeTrack(map,x + 1, y);
        }
        if (y + 1 < cols && map[x][y + 1] == 0){ //右
            mazeTrack(map, x , y + 1);
        }
        map[x][y] = 0;
        tempPath.pop();
    }
}
编辑于 2019-06-12 20:54:56 回复(0)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<ctype.h>

using namespace std;

void dfs(int x,int y,stack<string> s);// 深度搜索 s用来存放坐标路径
bool check_ok(int x,int y);          // 判断每个坐标是否可行(剪枝)
string to_string(int x,int y);         //把坐标转为字符串形式

vector<vector<int>> vec(11, vector<int> (11) );    //存放地图
vector<vector<int>> book(11,vector<int> (11));        //标记地图对应的点是否走过
stack<string> s;                                    //存放路径的栈,作为dfs函数的参数
stack<string> res;                                    //最终结果栈
bool flag=true;                                      //标志位

int main()
{
   while(cin>>COL>>ROW)
    {               for (int i = 0; i < 11; i++)         {             for (int j = 0; j < 11; j++)             {                 vec[i][j]=0;                 book[i][j]=0;             }         }         flag=true;         while (!s.empty())         {             s.pop();         }  
        for(int i=0;i<=COL;i++)
        {
            for(int j=0;j<=ROW;j++)
            {
                vec[i][j]=1;
            }
        }
     
        for(int i=1;i<=COL;i++)
        {
            for(int j=1;j<=ROW;j++)
            {
                cin>>vec[i][j];
            }
        }
        
//前面的操作均为初始化操作

        string st="(0,0)";
        s.push(st);
        dfs(1,1,s);
               stack<string> last;         int leng=res.size();         for (int i = 0; i < leng; i++)         {                     last.push(res.top());             res.pop();         }                        for (int i = 0; i < leng; i++)         {             cout<<last.top()<<endl;             last.pop();         }
     
    }

    return 0;
}

void dfs(int x,int y,stack<string> s)
{
    if(x==COL&&y==ROW)
    {         if (flag)         {             flag=false;             res=s;         }         else         {             if (res.size()>s.size())             {                 res=s;             }         }            
    }
  
    else
    {
        int next[2][4]=
        {
            1,-1,0,0,
            0,0,1,-1
        };
        int tx,ty;
        for(int i=0;i<4;i++)
        {
            tx=x+next[0][i];
            ty=y+next[1][i];
            if(check_ok(tx,ty))
            {
                book[tx][ty]=2;
                s.push( to_string(tx,ty));
                dfs(tx,ty,s);
                book[tx][ty]=0;
                s.pop();
            }
        }
    }
}
bool check_ok(int x,int y)
{     if (x<1||x>COL||y<1||y>ROW)     {         return false;     }
    if(book[x][y]==2)
        return false;
    if( vec[x][y]==1  )
        return false;
    return true;
}

string to_string(int x,int y)
{    --x,--y;     char temp[10]="( , )";     char a=x+'0';     char b=y+'0';     temp[1]=a;     temp[3]=b;     string st=temp;     return st;     }

发表于 2019-05-05 12:27:45 回复(0)
#include <bits/stdc++.h>

using namespace std;

int N,M;
vector<vector<int>> G;
vector<vector<int>> Path;
vector<vector<int>> temp;

void T(int i, int j)
{     G[i][j] = 1;     temp.push_back({i,j});          if(i==N-1 && j==M-1)         if(Path.empty() || temp.size() < Path.size())             Path = temp;          if(i>0 && G[i-1][j]==0)         T(i-1,j);     if(i<N-1 && G[i+1][j]==0)         T(i+1,j);     if(j>0 && G[i][j-1]==0)         T(i,j-1);     if(j<M-1 && G[i][j+1]==0)         T(i,j+1);              G[i][j] = 0;     temp.pop_back();
}
 
int main()
{     while(cin>>N>>M)      {         G = vector<vector<int>> (N,vector<int>(M,0));         Path.clear();         temp.clear();         for(int i=0;i<N;i++)             for(int j=0;j<M;j++)                 cin>>G[i][j];         T(0,0);         for(int i=0;i<Path.size();i++)             printf("(%d,%d)\n", Path[i][0], Path[i][1]);          }     return 0;
}

发表于 2019-01-06 00:26:29 回复(0)