输出所有路径 P137

//dfs暴搜所有路径
//蓝桥杯算法竞赛p137
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define endl "\n"
using namespace std;
const int N = 15;
int n,l;
char m[N][N];
string p[N][N];//i到j的路径记录
int x1 , x2 , y1, y2;
int sx , sy, tx, ty;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int num;
void dfs(int x , int y){
    for(int i = 0 ; i < 4 ; i ++){
        int nx = x + dx[i] , ny = y + dy[i];
        if(nx >= n || nx < 0 || ny >= l || ny < 0 ) continue ;//走出地图，超范围了
        if(m[nx][ny] == '*'){//遇到终点         
            num ++ ;//路径加一
            char  t[4]; sprintf(t,"%d%d",nx,ny);//把整数变量变成字符串变量
            cout << num << ": " << p[x][y] << "->" << t << endl ;//输出路径
            //会有覆盖
            continue ;
        }
        if(m[nx][ny] == '.'){
            m[nx][ny] = '#';//标记已经走过
            char t[4] ; sprintf(t,"%d%d",nx,ny);
            p[nx][ny] = p[x][y] + "->" + t ;//记录路径
            dfs(nx,ny);
            m[nx][ny] = '.';
        }
    }
}
 
 
int main(){
    cin >> l >> n ;
    for(int i = 0 ; i < l ; i ++){
        for(int j = 0 ; j < n ; j ++){
            cin >> m[j][i] ;
            if(m[j][i] == '@') { sx = j ; sy = i ;}
            if(m[j][i] == '*') { tx = j ; ty = i ;}
        }
    }
    cout << "from" << sx << sy << " to " << tx << ty << endl ;//记录起点
    char t[4] ;  sprintf(t,"%d%d",sx , sy); p[sx][sy] = t;
    dfs(sx,sy);
    return 0;
}