题解：P13348 「ZYZ 2025」未选择的路

思路

观察subtask，发现要根据

n

的奇偶性分类讨论。

n

为奇数时没什么好说的，一层层走折线就可以经过所有方格。

重点是

n

为偶数的情况，这时肯定是走不到所有的方格的。最多走到

n(n - 1)

个方格。下面以

n = 6

为例：

~~手画的，难看勿喷~~

最优情况下，左上到右下的对角线上的方格是走不到的。采用从外到内的走法，从当前最外层的右下角走起，折线走过四条边最后回到右下角，接着走下一圈，之后补齐右上到左下的对角线即可。实现时可以采用递归的方式。

code

CPP

//头文件太长删掉了
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
#define _rof(i,a,b) for(int i=(a);i>=(b);i--)
#define max(a,b) a>=b ? a:b
#define min(a,b) a<b ? a:b
using namespace std;
inline void solve(int x){
    printf("%d %d\n",x,x);
    if(x==n/2)return;

    int flg=1;
    _for(i,x+1,n-x){
        printf("%d %d\n",i,x-flg);
        flg^=1;
    }
    _for(i,x+1,n-x){
        printf("%d %d\n",n-x+flg,i);
        flg^=1;
    }
    _rof(i,n-x-1,x){
        printf("%d %d\n",i,n-x+flg);
        flg^=1;
    }
    _rof(i,n-x-1,x){
        printf("%d %d\n",x-flg,i);
        flg^=1;
    }

    solve(x+1);
}
signed main(){
    scanf("%d",&n);
    if(n&1){
        printf("%d\n",n*n);
        _for(i,1,n){
            if(i%2){
                _for(j,1,n)
                    printf("%d %d\n",j,i+((j%2==1)?0:-1));
            }else{
                _rof(j,n-1,0)
                    printf("%d %d\n",j,i+((j%2==0)?0:-1));
            }
        }
    }else{
        printf("%d\n",n*(n-1));
        solve(1);
        _for(i,n/2+1,n) printf("%d %d\n",i,i);
    }
    return 0;
}

AC记录

题解：P13348 「ZYZ 2025」未选择的路

文章操作

思路

code

相关推荐

评论

题解：P13348 「ZYZ 2025」未选择的路