不定次数循环(应该是) #8 WA 求优化帮助 (内有较详细问题描述)
  • 板块P1443 马的遍历
  • 楼主kinorw
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/1/8 12:52
  • 上次更新2023/10/24 05:11:14
查看原帖
不定次数循环(应该是) #8 WA 求优化帮助 (内有较详细问题描述)
745936
kinorw楼主2023/1/8 12:52

本来是准备写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点),个人神志不清,导致发布内容个人感觉没有详细描述问题 ,留言补充又不便阅读,故删除重发此帖

2023/1/8 12:52
加载中...