迷宫、走方格

一、迷宫

#include<vector>
#include<cstring>
using namespace std;
int m,n; /*m 行，n 列*/
vector<pair<int,int>> dirc;
/*存储1，0 的二维数组*/
int arr[11][11]={0};
/*存储标记的二维数组*/
int tab[11][11]={0};
/*定义四个方向的坐标用于上下左右移动*/
int dir[4][2]={{0,1},/*左移*/
               {0,-1},/*右移*/
               {1,0},/*下移*/
               {-1,0}/*上移*/

};
bool dfs(int x,int y){
    int p,q;/*p 行 q 列*/
    if(x==m-1 && y==n-1){
        return true;
    }
    for(int i=0;i<4;i++){
        p=x+dir[i][0];
        q=y+dir[i][1];
        if(p>=0 && p<m && q>=0 && q<n){
            if(arr[p][q]==0 && tab[p][q]==0){
                tab[p][q]=1;
                if(dfs(p,q)){
                    dirc.push_back(make_pair(p,q));
                    return true;
                }
            }
        }
    }
    return false;
}
int main(void){
    int i,j;
    while(cin>>m>>n){
    /*输入数据*/ 
        for(i=0;i<m;i++){
            for(j=0;j<n;j++){
                cin>>arr[i][j];
            }
        }
    /*递归输出符合的坐标*/
        tab[0][0]=1;
        cout<<"(0,0)"<<endl;
        if(dfs(0,0)==true){
            auto it=dirc.rbegin();
            while(it!=dirc.rend()){
                cout<<"("<<it->first<<","<<it->second<<")"<<endl;
                it++;
            }
        }
        dirc.clear();
        memset(tab,0,sizeof(tab));
    }
    return 0;
}

二、走方格 题目

#include<cstring>
using namespace std;
int arr[10][10];
int tab[10][10]={0};
int dir[2][2]={{0,1},{1,0}};
int n,m  /*n 横 m竖*/;
int num=0; /*总走法*/

void dfs(int x,int y){
    int p,q;
    if(x==n-1 && y==m-1){
        num++;
    }
    for(int i=0;i<2;i++){
        p=x+dir[i][0];
        q=y+dir[i][1];
        if(p<n && q<m){
            if(tab[p][q]==0){
                dfs(p,q);
            }
        }
    }
    return ;
}/*
.  .   .
.  .   .
.  .   .*/
int main(void){
    while(cin>>n>>m){
        n++;
        m++;
        dfs(0,0);
        cout<<num<<endl;
        num=0;
        memset(tab,0,sizeof(tab));
        
    }
    return 0;
}