[游戏开发]落谷P1189 `SEARCH`

落谷P1189 `SEARCH`

`SEARCH` - 洛谷https://www.luogu.com.cn/problem/P1189本题使用递归算法，核心代码中for里面两个if判断进入下一层递归的条件,如果撞墙或出格,都会终止for循环。否则进入下一层递归.

int n,m;
        int board[31][31];
        int xs,ys;
        int x[4]={-1,1,0,0};//
        int y[4]={0,0,1,-1};
        bool pass[51][51];//是否能通过
        char s[51][51];//地图
        int way[1001];//接收移动方向
        int nn;
        void search(int heng,int zong,int step){//"heng""zong"为坐标,step为步数
            if(step==nn){
                s[heng][zong]='*';//到终点,改变符号
                return;
            }
            int heng1=heng,zong1=zong;
            for(int i=0;i<51;i++){
                heng1+=x[way[step]];//"移动"到下一格
                zong1+=y[way[step]];
                if(heng1<0||heng1>=n||zong1>=m||zong1<0){//判断是否会超出地图
                    break;
                }
                if(pass[heng1][zong1]==0){//判断是否会进入禁行区
                    break;
                }
                search(heng1, zong1, step+1);//进入下一层递归
            }
            
        }
        int main(){
            cin>>n>>m;
            for(int i=0;i<n;i++){//输入pass
                for(int j=0;j<m;j++){
                    cin>>s[i][j];
                    if(s[i][j]=='.'){
                        pass[i][j]=1;
                    }else if(s[i][j]=='X'){
                        pass[i][j]=0;
                    }else{
                        pass[i][j]=1;
                        xs=i;
                        ys=j;
                    }
                }
            }
            cin>>nn;
            for(int i=0;i<nn;i++){//设置way
                string str;
                cin>>str;
                if(str=="NORTH"){
                    way[i]=0;
                }else if(str=="SOUTH"){
                    way[i]=1;
                }else if(str=="EAST"){
                    way[i]=2;
                }else{
                    way[i]=3;
                }
            }
            search(xs,ys,0);
            s[xs][ys]='.';
            for(int i=0;i<n;i++){//输出
                for(int j=0;j<m;j++){
                    cout<<s[i][j];
                }
                cout<<endl;
            }

            return 0;
        }