迷宫问题

#include <stdbool.h>
#include <stdio.h>
  
int arr[11][11] = {0}; 
int markRow[100]; 
int markVol[100];  
int countMark = 0;  
int row = 11;
int vol = 11;
int rowMove[4] = {1, 0, -1, 0};  
int volMove[4] = {0, 1, 0, -1};  
  
bool boundary(int x, int y) {  
    if (x < 0 || y < 0 || x >= row || y >= vol)  
        return false;  
    return true;  
}  
  
void dfs(int x, int y) {  
    if (x == row - 1 && y == vol - 1) { // 到达右下角  
        for (int i = 0; i < countMark; i++) {  
            printf("(%d,%d)\n", markRow[i], markVol[i]);  
        }  
        return; // 不需要继续搜索  
    }  
    for (int i = 0; i < 4; i++) {  
        int nx = x + rowMove[i];  
        int ny = y + volMove[i];  
        if (boundary(nx, ny) && arr[nx][ny] == 0) { // 确保在边界内且未访问过  
            markRow[countMark] = nx;  
            markVol[countMark] = ny;  
            arr[nx][ny] = 1; // 标记为已访问  
            countMark++;  
            dfs(nx, ny); // 递归搜索  
            countMark--; // 回溯时取消标记  
            arr[nx][ny] = 0; // 回溯时取消访问标记  
        }  
    }  
}  

int main() {
    scanf("%d%d", &row,&vol);
    for (int i = 0; i < row; i++){
        for(int j = 0; j < vol; j++)
        {
            scanf("%d", &arr[i][j]);
        }
    }
    printf("(0,0)\n");
    dfs(0 ,0);
    return 0;
}

第一次用DFS做题，向掌握DFS前进一小步 
#include <stdio.h>

int next[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int mark[10][10];
int path[100][2];

int main() {
    int row,col;
    int map[10][10];
    void dfs(int x,int y,int step,int row,int col,int next[4][2],int map[10][10]);
    while (scanf("%d %d", &row, &col) != EOF) { 
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                scanf("%d",&map[i][j]);
    mark[0][0] = 1;
    path[0][0] = 0;
    path[0][1] = 0;
    dfs(0,0,1,row,col,next,map);
    }
    return 0;
}

void dfs(int x,int y,int step,int row,int col,int next[4][2],int map[10][10]){
    int nx,ny,i;
    if(x==row-1&&y==col-1){
        for(int j=0;j<step;j++){
            printf("(%d,%d)\n",path[j][0],path[j][1]);
        }
        return;
    }
    if(map[x][y]==1){
        return;
    }
    for(i=0;i<4;i++){
        nx = x + next[i][0];
        ny = y + next[i][1];
        if(nx<0||nx>row-1||ny<0||ny>col-1)
            continue;
        if(mark[nx][ny]==0){
            path[step][0] = nx;  //保存路径
            path[step][1] = ny;
            mark[nx][ny]=1;
            dfs(nx,ny,step+1,row,col,next,map);
            mark[nx][ny]=0;
        }
    }
}

#include <stdio.h>

void f(int *a,int *b,int x ,int y ,int i,int pos);

int n,m;        //n行，m列；

int main() {
    
    scanf("%d %d",&n,&m);
    int a[n*m];
    for(int i=0 ; i<m*n ;i++)   scanf("%d",&a[i]);
    int b[200]={0};
    int i=0,j=0;

    f(a,b,0,0,0,0);
    return 0;
}

void f(int *a,int *b ,int x , int y ,int i,int pos){
    b[i*2]=x;
    b[i*2+1]=y;
    if(x==n-1&&y==m-1)  {
        for(int j=0 ,k=0;j<i+1;j++,k+=2)
        printf("(%d,%d)\n",b[k],b[k+1]);
    }

    int derication[4]={1,1,1,1};
    if(y==0||pos==3||a[x*m+y-1]==1) derication[3]=0; //不能朝左
    if(y==m-1||pos==1||a[x*m+y+1]==1) derication[1]=0; //不能向右
    if(x==0||pos==0||a[(x-1)*m+y]==1) derication[0]=0; //不能向上
    if(x==n-1||pos==2||a[(x+1)*m+y]==1) derication[2]=0; //不能向下
    if(derication[0]) f(a, b,  x-1,  y,  i+1,  2);
    if(derication[1]) f(a, b,  x,  y+1,  i+1,  3);
    if(derication[2]) f(a, b,  x+1,  y,  i+1,  0);
    if(derication[3]) f(a, b,  x,  y-1,  i+1,  1);
 
    
}
// 不受控制的递归，只好在经过终点时赶紧输出了，我该怎么办？

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#include<assert.h>

#include<string.h>

#include<errno.h>

//定义一个结构体存储当前的位置坐标

typedef struct Position{

    int row;

    int col;

}Pos;

//////////////////////////进行栈相关代码的编写

typedef Pos STDataType;

typedef struct Stack {

    STDataType* a;

    int top;

    int capacity;

}ST;

//定义一个全局栈，用于存储迷宫中的节点

ST Path;

void StackInit(ST* head);

void StackPush(ST* head, STDataType x);

void StackPrint(ST* head);

void StackPop(ST* head);

void StackDestroy(ST* head);

bool StackEmpty(ST* head);

void StackInit(ST* head)    //栈的初始化

{

    head->a = NULL;

    head->top = 0;  //head->top=-1

    head->capacity = 0;

}

bool StackEmpty(ST* head)

{

    assert(head);

    return head->top == 0;//栈为空返回ture，栈为假返回false

}

void StackPush(ST* head, STDataType x)   //从栈顶插入元素

{

    assert(head);

    if (head->top == head->capacity)

    {

        int newcapacity = head->top == 0 ? 4 : 2 * head->capacity;

        STDataType* tmp = (STDataType*)realloc(head->a, sizeof(STDataType)*newcapacity);

        if (tmp == NULL)

        {

            printf("%s\n",strerror(errno));

            exit(-1);

        }

        head->a = tmp;

        head->capacity = newcapacity;

    }

    head->a[head->top] = x;

    head->top++;

}

void StackPop(ST* head)     //从栈顶删除元素

{

    assert(head);

    //assert(head->top);

    assert(!StackEmpty(head));//此语句与上面一条语句具有等效作用

    head->top--;

}

STDataType StackTop(ST* head)//取栈顶元素

{

    assert(head);

    /*assert(head->top>0);*/

    assert(!StackEmpty(head));

    return (head->a)[head->top-1]; //此处只能是head->top-1,不能改变为--head->top，这样会改变top的值

}

void StackDestroy(ST* head)   //销毁栈

{

    assert(head);

    free(head->a);

    head->top = head->capacity = 0;

}

//////////////////////////

bool IstruePath(int**maze,int N,int M,Pos cur)

{

    if(cur.row>=0&&cur.row<N

    &&cur.col>=0&&cur.col<M

    &&maze[cur.row][cur.col]==0)

        return true;

    else

        return false;

}

bool GetMazePath(int** maze,int N,int M,Pos cur)

{

    StackPush(&Path,cur);

    if(cur.row==N-1&&cur.col==M-1)

        return true;

    //将走过的坐标标记为2

    maze[cur.row][cur.col]=2;

    Pos next;

    //进行上、下、左、右四个方位的遍历

    //上

    //每次遍历上、下、左、右时都需要将cur赋给next，每次遍历的时候都会改变当前next中不同方向坐标的值

    next=cur;    //

    next.row-=1;

    if(IstruePath(maze,N,M,next))

    {

        if(GetMazePath(maze,N,M,next))

            return true;

    }

    //下

    next=cur;

    next.row+=1;

    if(IstruePath(maze,N,M,next))

    {

        if(GetMazePath(maze,N,M,next))

            return true;

    }

    //左

    next=cur;

    next.col-=1;

    if(IstruePath(maze,N,M,next))

    {

        if(GetMazePath(maze,N,M,next))

            return true;

    }

    //右

    next=cur;

    next.col+=1;

    if(IstruePath(maze,N,M,next))

    {

        if(GetMazePath(maze,N,M,next))

            return true;

    }

    StackPop(&Path);

    return false;

}

void PrintPath(ST* path)

{

    ST tpath;

    StackInit(&tpath);

    while(!StackEmpty(path))

    {

        StackPush(&tpath,StackTop(path));

        StackPop(path);

    }

    while(!StackEmpty(&tpath))

    {

        Pos pos=StackTop(&tpath);

        StackPop(&tpath);

        printf("(%d,%d)\n",pos.row,pos.col);

    }

    StackDestroy(&tpath);

}

int main() {

    int N,M;

    while(scanf("%d %d",&N,&M)!=EOF)

    {

            //开辟动态二维数组

        int** maze=(int**)malloc(sizeof(int*)*N);

        for(int i=0;i<N;i++)

        {

            maze[i]=(int*)malloc(sizeof(int)*M);

        }

        //进行数据的录入

        for(int i=0;i<N;i++)

        {

            for(int j=0;j<M;j++)

            {

                scanf("%d",&maze[i][j]);

            }

        }

        //Print(maze,N,M);  //验证开辟数组的正确性

        //进行遍历得到路径,Pos中进行存储当前位置坐标

        StackInit(&Path);

        Pos empty={0,0};

        PrintPath(&Path);

        if(GetMazePath(maze,N,M,empty))

        {

            PrintPath(&Path);

        }

        else

        {

            printf("The maze Path Is Not\n");

        }

        StackDestroy(&Path);

        //释放开辟的动态二维数组

        for(int i=0;i<N;i++)

        {

            free(maze[i]);

        }

        free(maze);

    }

    return 0;

}

#include <stdio.h>

int m, n;//入口为（0,0）
int arr[10][10] = { {1} };//0代表空地，1代表墙
int v[10][10] = { {0} };//0代表为访问，1代表已访问
int stack[100][2] = { {0,0} };//栈，存放已走的路径
int step = 0;//存放步骤数，充当栈的指针
int flag = 0;//表示正确道路已找到，1为已找到
int dx[4] = { 0,1,0,-1 };//右，下，左，上
int dy[4] = { 1,0,-1,0 };//右，下，左，上

void push(int x1, int y1)//把步骤入栈
{
	stack[step][0] = x1;
	stack[step][1] = y1;
}

void dfs(int x,int y)//使用dfs的方法，找出路径
{
	if (x == m-1 && y == n-1)//判断是否到达终点（m-1,n-1）
	{
		flag = 1;
		return;
	}
	for (int k = 0; k < 4; k++)//判断当前点位可以走哪个方向
	{
		int tx, ty;
		tx = x + dx[k];
		ty = y + dy[k];
		if (arr[tx][ty] == 0 && v[tx][ty] == 0)
		{
			step++;
			push(tx, ty);//把下一步入栈
			v[tx][ty] = 1;//标记下一步为已访问点位
			dfs(tx, ty);//确认可走后，进入下一步，重复dfs
			if (flag == 1)
				return;
			step--;
			v[tx][ty] = 0;//标记释放  回溯前的点位  为  未访问点位
		}
	}
	return;
}

/*
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*/

int main()
{
	//输入实际迷宫大小
	scanf("%d %d", &m, &n);

	int i = 0;
	int j = 0;
	//初始化最大迷宫
	for (i = 0; i < 10; i++)
		for (j = 0; j < 10; j++)
			arr[i][j] = 1;


	//输入题目中的迷宫
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			scanf("%d", &arr[i][j]);

	dfs(0, 0);//起始位置为(0,0)

	for (int i = 0; i <= step; i++)
	{
		printf("(%d,%d)\n", stack[i][0], stack[i][1]);
	}
	
	return 0;
}

#include <stdio.h>

struct PATH
{
  int x;
  int y;
  struct PATH *father;
};


int main()
{
  int i, j, k, n, m, x, y, z;
  
  scanf("%d %d", &n, &m);
    
  int maze[n][m];
  struct PATH path[n * m];
  
  for(i = 0; i < n; i++)
    for(j = 0; j < m; j++)
      scanf("%d", &maze[i][j]);
  
  maze[0][0] = 1;
  k = 0;
  path[k].x = 0;
  path[k].y = 0;
  while(1)
  {
    x = path[k].x;
    y = path[k].y;
    z = 0;
    
    if(x >= n - 1 && y >= m - 1)
      break;
    
    if(x < n - 1 && maze[x + 1][y] == 0)
    {
      x++;
      z = 1;
    }
    else if(y < m - 1 && maze[x][y + 1] == 0)
    {
      y++;
      z = 1;
    }
    else if(x > 0 && maze[x - 1][y] == 0)
    {
      x--;
      z = 1;
    }
    else if(y > 0 && maze[x][y - 1] == 0)
    {
      y--;
      z = 1;
    }
    
    if(z)
    {
      k++;
      maze[x][y] = 1;
      path[k].x = x;
      path[k].y = y;
    }
    else
    {
      k--;
    }
  }
  
  for(i = 0; i <= k; i++)
  {
    printf("(%d,%d)\r\n", path[i].x, path[i].y);
  }
}

#include <stdio.h>
#define    N    10
int sign[N][N],pos[1000][2],n,m,cnt,maze[N][N],flag;
void dfs(int x,int y)
{
    pos[cnt][0]=x;pos[cnt][1]=y;cnt++;
    sign[x][y]=1;
    if(x==n-1&&y==m-1)
    {
        flag=1;
        return;
    }
    int i,j,k;
    int x_incre[4]={0,1,0,-1},y_incre[4]={1,0,-1,0};
    for(k=0;k<4;k++)
    {
        i=x+x_incre[k];j=y+y_incre[k];
        if(i>=0&&j>=0&&i<n&&j<m&&!maze[i][j]&&!sign[i][j])
        {
            dfs(i,j);
            if(flag)
                return;
        }
    }
    sign[i][j]=0;
    cnt--;
}
int main()
{
    int i,j,startx=0,starty=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            scanf("%d",&maze[i][j]);
    dfs(startx,starty);
    for(i=0;i<cnt;i++)
        printf("(%d,%d)\n",pos[i][0],pos[i][1]);
    return 0;
}

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int N, M;
int visit[10][10];

void Solve_Maze(int Raw, int Column, int *p)
{
    if(Raw < 0 || Raw >= N || Column < 0 || Column >= M)
        return;
    if((Raw == N-1) && (Column == M-1))
    {
        visit[Raw][Column] = 2;
        return;
    }
    if(*(p + Raw * M + Column) == 0 && visit[Raw][Column] == 0)    
    {
        visit[Raw][Column] = 1;
        Solve_Maze(Raw-1, Column, p);//上
        if(visit[Raw-1][Column] == 2)
        {
            visit[Raw][Column] = 2;
            return;
        }
        Solve_Maze(Raw+1, Column, p);//下
        if(visit[Raw+1][Column] == 2)
        {
            visit[Raw][Column] = 2;
            return;
        }
        Solve_Maze(Raw, Column-1, p);//左
        if(visit[Raw][Column-1] == 2)
        {
            visit[Raw][Column] = 2;
            return;
        }
        Solve_Maze(Raw, Column+1, p);//右
        if(visit[Raw][Column+1] == 2)
        {
            visit[Raw][Column] = 2;
            return;
        }
    }
    
    else
        return;
}


int main()
{
    while(scanf("%d%d", &N, &M) != EOF)
    {
        memset(visit, 0, sizeof(visit));
        int maze[N][M];
        int i = 0;
        int j = 0;
        for(i=0; i<N; i++)
            for(j=0; j<M; j++)
                scanf("%d", &maze[i][j]);
        Solve_Maze(0, 0, *maze);
        /*输出*/
        i = j = 0;
        while((i != N-1) || (j != M-1))
        {
            printf("(%d,%d)\n", i, j);
            visit[i][j] = 3;//已输出
            if(visit[i-1][j] == 2)
                i--;
            else if(visit[i+1][j] == 2)
                i++;
            else if(visit[i][j-1] == 2)
                j--;
            else if(visit[i][j+1] == 2)
                j++;
        }
        printf("(%d,%d)\n", i, j);
          
    }
    return 0;
}