很自然的一道题，没有晦涩难懂的算法，思考全面是关键

解题思路:

注释已经比较清晰了

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 105

int tu[maxn][maxn];//tu[i][j]为0表示未定，为1表示为迷宫内空地，

//为2表示为墙，为3表示迷宫外空地 

unordered_map<char,int> dire;

int n,step[maxn];

int initx,inity;//初始位置的横纵坐标，比如样例中的initx=6,inity=6 

int hangshu,lieshu;//整个图的行数和列数，比如样例中的hangshu为7，lieshu为7 

int mymove[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

bool vis[maxn][maxn]; 

void getinfor(){

int x=0,y=0;

initx=max(initx,x+2);

inity=max(inity,y+2);

for(int i=1;i<=n;i++){

    switch(step[i]){

    case 1:

    x++;

    initx=max(initx,x+2);

    break;

    case 2:

    x--; 

    break;

    case 3:

    y++;

    inity=max(inity,y+2);

    break;

    case 4:

    y--;

    break;

}

}

}

void dfs(int x,int y){

for(int i=1;i<=n;i++){

tu[x][y]=1;

hangshu=max(hangshu,x);

lieshu=max(lieshu,y); 

    switch(step[i]){

    case 1:

    x--;

    break;

    case 2:

    x++; 

    break;

    case 3:

    y--;

    break;

    case 4:

    y++;

    break;

}

}

tu[x][y]=1;

hangshu=max(hangshu,x);

lieshu=max(lieshu,y); 

hangshu++;

lieshu++;//因为右边和上边要有墙 

}

void dfs1(int x,int y)//这是因为围墙可能围住了一部分爱丽丝没走过的地方，需要将这些地方置为围墙

/*

比如

 *****

*     *

* *** *

* *X* *

* *X* *

* *** *

*     *

 *****

标X的地方没被走过，但被围墙围住了 

*/ 

{

int nextx,nexty;

for(int i=0;i<4;i++){

nextx=x+mymove[i][0];

nexty=y+mymove[i][1];

if(tu[nextx][nexty]==0&&1<=nextx&&nextx<=hangshu&&1<=nexty&&nexty<=lieshu){

tu[nextx][nexty]=3;

dfs1(nextx,nexty);

}

}

}

int main(){

    scanf("%d",&n);

    dire['U']=1;

    dire['D']=2;

    dire['L']=3;

    dire['R']=4;

    string str;

    cin>>str;

    for(int i=1;i<=n;i++){

    step[i]=dire[str[i-1]];

}

memset(tu,0,sizeof(tu)); 

getinfor();//根据step[]获取一些信息 

dfs(initx,inity);

for(int i=1;i<=hangshu;i++){

for(int j=1;j<=lieshu;j++){

vis[i][j]=1; 

if(tu[i][j]==0){//这个元素未定 

if(tu[i-1][j]==1||tu[i+1][j]==1||tu[i][j-1]==1||tu[i][j+1]==1){

tu[i][j]=2;//设置为围墙 

}

}

}

}

for(int i=1;i<=hangshu;i++){

if(i==1||i==hangshu){

for(int j=1;j<=lieshu;j++){

if(tu[i][j]==0){

tu[i][j]=3;//置为迷宫外空地 

dfs1(i,j);

}

    }

}

else{

if(tu[i][1]==0){

tu[i][1]=3;

dfs1(i,1);

}

if(tu[i][lieshu]==0){

tu[i][lieshu]=3;

dfs1(i,lieshu);

}

}

}

//以下是输出 

for(int i=1;i<=hangshu;i++){

for(int j=1;j<=lieshu;j++){

if(tu[i][j]==2||tu[i][j]==0)printf("*");

else printf(" ");

}

putchar('\n');

}

return 0;

}