1 条题解

  • 0
    @ 2023-4-1 9:23:19
    #include <iostream>
    using namespace std;
    const int M =100;//规模n行,m列,不超过100 
    char maze[M][M];//LQBS
    bool visited[M][M]={0};//是否访问,如在一次向前搜索中,会访问到已经标记已访问的结点,则存在环
    //允许重复访问 
    int n,m;// n行,m列
    int steps=1; 
    int ans=0;
    typedef struct LNode
    {
    	int lx,ly;// 位置信息 
    	bool visited; 
    }LNODE;
    int SLcount=0;//L点个数 
    //四个方向维度 
    int dx[]={1,0,-1,0};// 行 的变化量 
    int dy[]={0,1,0,-1};//列的变化量 
    int searchLQBS(int,int,LNODE *);//搜索算法 
    int main()
    {
    	cin>>n>>m;
    	LNODE SL[n*m+1];//存储所有L结点 
    	for(int i=1;i<=n;i++)//行
        {
    	    for(int j=1;j<=m;j++)
    	    {
    	 	    cin >> maze[i][j];
    	 	    if(maze[i][j]=='L')
                {
    	 		    SL[SLcount].lx=i;SL[SLcount].ly=j;
    	 		    SL[SLcount++].visited=0; 
    		    }	
    	    }
        }
    	for(int i=0;i<SLcount;i++)//枚举所有开始点
    	{//可以剪枝,一次深度搜索中,所有访问过的L点,不需要再次搜索
    	if(SL[i].visited==0)
    	{
    	 	visited[SL[i].lx][SL[i].ly]=1;
    	 	int result=searchLQBS(SL[i].lx,SL[i].ly,SL);
    	 	visited[SL[i].lx][SL[i].ly]=0;//清零,回溯 
    	    //steps=1; 
    	 	if(result)
    	 	{
    	 		ans=-1;
    	 		break;
    		}
    	 }
    	} 
        cout<<ans;
    	return 0;
    } 
    int searchLQBS(int lx,int ly,LNODE * SL)//从某个L点开始搜索 ,lx行,ly列 
    {
    	if(maze[lx][ly]=='L')
    	   for(int j=0;j<SLcount;j++)
    	     if(SL[j].lx==lx && SL[j].ly==ly) SL[j].visited=true;
    	char quachar;
    	if(maze[lx][ly]=='L') quachar='Q';    
    	if(maze[lx][ly]=='Q') quachar='B'; 
    	if(maze[lx][ly]=='B') quachar='S';    
    	if(maze[lx][ly]=='S') quachar='L'; 
    	for (int i=0;i<4;i++)
    	{
    		int xx=lx+dx[i];
    		int yy=ly+dy[i];
    		if(xx>0 && yy>0 && xx<=n && yy<=m && maze[xx][yy]==quachar && visited[xx][yy])
    		return -1;
    		else if(xx>0 && yy>0 && xx<=n && yy<=m && maze[xx][yy]==quachar){
    		visited[xx][yy]=1;
    		steps+=1;
    		if(searchLQBS(xx,yy,SL)==-1) return -1;
    		visited[xx][yy]=0;
    		//回溯前, 反复计算循环次数
    		if((steps/4)>ans) ans=steps/4;
    		steps--;			
    		}
    	}
    	return 0;
    }//已AC
    
    • 1

    信息

    ID
    946
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者