本来是准备写dfs的但是爆了,优化不动,索性魔改成了这个感觉像是不定次数循环的东西
存在问题:初步估计为部分区域(数据为199 199 100 100时体现为左上角 左下角 居中偏上一小块)无法进入(即为-1)
但经尝试数据(199 199 50 50)时发现并非无法进入,而是为某个次数时,某些位置不能进一步搜索了(体现为输出观察到68的右下角为106等,而67左下角为-1)
固判断106为后续某次搜索延续过来的,但此前为什么不能进入该区域进行复制,蒟蒻没有头绪
恳请各位大佬指点
//因为一开始思路不明确,数据命名有些难懂,在此注释:
sum tag[numb]均为记录该次循环共搜索到几个点,sum用来判断外(大)循环是否结束,tag用来协助记录点的坐标,判断小(内)循环执行次数
q,p数组分别记录第numb次循环(搜索)时标记的点x,y值
//
#include<stdio.h>
int a[405][405],n,m,numb=1,tag[405],sum,q[405][405],p[405][405];
int flag[405][405];
void search(int x,int y)
{
if(x<=0||y<=0||x>n||y>m||flag[x][y]==1)
return;
a[x][y]+=numb;
flag[x][y]=1;
q[numb][tag[numb]]=x;
p[numb][tag[numb]]=y;
tag[numb]++;
sum++;
}
int main()
{
int x,y;
scanf("%d%d%d%d",&n,&m,&x,&y);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
a[i][j]=-1;
}
search(x,y);
while(sum)
{
numb++;
sum=0;
while(tag[numb-1])
{
tag[numb-1]--;
x=q[numb-1][tag[numb-1]];
y=p[numb-1][tag[numb-1]];
search(x-2,y-1);
search(x-2,y+1);
search(x-1,y-2);
search(x-1,y+2);
search(x+2,y-1);
search(x+2,y+1);
search(x+1,y+2);
search(x+1,y-2);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%-5d",a[i][j]);
printf("\n");
}
return 0;
}
此前发过一个求助帖,但因在半夜(凌晨1点),个人神志不清,导致发布内容个人感觉没有详细描述问题 ,留言补充又不便阅读,故删除重发此帖