贺州学院LSY


私信TA

用户名:2371068703

访问量:6170

签 名:

等  级
排  名 441
经  验 4842
参赛次数 1
文章发表 10
年  龄 0
在职情况 学生
学  校 贺州学院
专  业 软件工程

  自我简介:

解题思路:

  DFS 核心代码,根据题意添加操作。

  

void DFS( 状态参数 ) {

    if ( 目的状态 ) {

      

        目的操作

        return;

    }

  

    for ( 搜索方式(移动) )

    {

        if ( 合法状态 ) {

          

            操作

            标记

              

            DFS( 更新状态参数 )

              

            回溯 ( 还原标记 )

        }

    }

}

   



注意事项:

参考代码:

#include <iostream>

using namespace std;

char a[100][100];

int x1,x2,y1,y2,n;

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

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

int vis[100][100];

int k=999999;

void dfs(int x,int y,int m)

{

    if(a[x][y]=='B')

    {

        if(k>m) k=m; 

        return ;

    }

}

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

{

    if(a[x][y]!=a[xx[i]+x][yy[i]+y] && xx[i]+x>0 && xx[i]+x<=n && yy[i]+y>0 && yy[i]+y<=n &&     !vis[xx[i]+x][yy[i]+y])

    {

        vis[xx[i]+x][yy[i]+y]=1;

        dfs(xx[i]+x,yy[i]+y,m+1);

        vis[xx[i]+x][yy[i]+y]=0;

     }

}

int main()

{


cin>>n;

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

{

    for(int j=1;j<=n;j++)

    {

        cin>>a[i][j];

        if(a[i][j]=='A'){x1=i;y1=j;}

        if(a[i][j]=='B'){x2=i;y2=j;}

    }

}


    dfs(x1,y1,0);

    cout<<k;

    return 0;

}


 

0.0分

1 人评分

  评论区

  • «
  • »