蒟蒻不会BFS,DFS加阀值仍TLE。评测记录
#include<iostream>
#include<cstdio>
using namespace std;
int ans[410][410];
int n,m;
int sx,sy;
void search(int x,int y,int sum)
{
if(sum>100)
{
return;
}
if(x<1||x>n||y<1||y>m)
{
return;
}
if((sum>ans[x][y]&&ans[x][y]!=0)||(x==sx&&y==sy))
{
return;
}
ans[x][y]=sum;
search(x+2,y+1,sum+1);
search(x-2,y+1,sum+1);
search(x+2,y-1,sum+1);
search(x-2,y-1,sum+1);
search(x+1,y+2,sum+1);
search(x-1,y+2,sum+1);
search(x+1,y-2,sum+1);
search(x-1,y-2,sum+1);
return;
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%d%d",&sx,&sy);
search(sx+2,sy+1,1);
search(sx-2,sy+1,1);
search(sx+2,sy-1,1);
search(sx-2,sy-1,1);
search(sx+1,sy+2,1);
search(sx-1,sy+2,1);
search(sx+1,sy-2,1);
search(sx-1,sy-2,1);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(i==sx&&j==sy)
{
printf("%-5d",0);
continue;
}
if(ans[i][j]==0)
{
printf("%-5d",-1);
continue;
}
printf("%-5d",ans[i][j]);
}
printf("\n");
}
return 0;
}