八个点TLE,最后一个WA,第二个点+样例能过,求大神帮忙!!!
查看原帖
八个点TLE,最后一个WA,第二个点+样例能过,求大神帮忙!!!
109678
Marshall_Left楼主2023/2/23 21:19
#include<bits/stdc++.h>
using namespace std;
int lx,ly,xx,yy;
int vis[401][401]={0};
int Map[401][401]={0};
struct Node
{
    int posx,posy,step;
} ;
int dx[8]={1,2,2,1,-1,-2,-2,-1};
int dy[8]={2,1,-1,-2,2,1,-1,-2};
queue<Node>Q;
int k(int c,int d,int a,int b)
{
	if(c==xx&&d==yy)
	return 0;
	if(b==0||(b>0&&b>a))
	return a;
	return b;
}
void bfs(int cnt)
{
    Node q=Q.front();
    Q.pop();
    int x=q.posx,y=q.posy;
    for(int k=0;k<8;k++)
    {
        int newx=x+dx[k],newy=y+dy[k];
        if(newx>=1&&newx<=lx&&newy>=1&&newy<=ly)
        {
            if(!vis[newx][newy])
            {
            	vis[newx][newy]++;
      Map[newx][newy]=k(newx,newy,q.step+1,Map[newx][newy]);
            Q.push({newx,newy,q.step+1});
            	bfs(cnt+1);
            	vis[newx][newy]--;
			}
        }
    }
    if(cnt==1)
    for(int i=1;i<=lx;i++)
    {
    	for(int j=1;j<=ly;j++)
    	cout<<left<<setw(5)<<Map[i][j];
    	cout<<endl;
	}
    return ;
}
int main()
{  
	memset(Map,0,sizeof(Map));
    memset(vis,0,sizeof(vis));
    cin>>lx>>ly>>xx>>yy;
    vis[xx][yy]=1;
    Map[xx][yy]=0;
    if(lx<=4&&ly<=4)
    for(int i=1;i<=lx;i++)
    {
        for(int j=1;j<=ly;j++)
        {
            int flag=0;
            for(int k=0;k<8;k++)
            {
            	if(i+dx[k]<=0||i+dx[k]>lx||j+dy[k]<=0||j+dy[k]>ly)
                flag++;
            }
            if(flag==8){
                Map[i][j]=-1;
            }
        }
    }
    Q.push({xx,yy,0});
    bfs(1);
    return 0;
}

初学dp回来复习的蒟蒻一枚,紧急求调!!

2023/2/23 21:19
加载中...