#P10509. 停车场

    ID: 9808 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>洛谷原创O2优化洛谷月赛Ad-hoc

停车场

题目描述

你有一片空地。这片空地可以视作一个一个 n×nn\times n 的正方形。空地外一圈为墙壁,你无法拆除它们。

现在你要在这片空地上规划停车位,使之成为一个停车场。你希望空地的左下角是停车场的出入口。出入口不能规划为停车位。空地和停车位都是 1×11\times 1 的正方形,且正方形的每条边与墙壁平行或者垂直。

每个停车位都应该与至少一个空地四连通(即:停车场的上、下、左、右方至少有一个空地),且这个空地应当能通过若干次向上、下、左、右的移动,在不经过任何停车位的情况下到达出入口。

下图为 n=4n=4 时停车位数最多的放置方法之一,其中红色为车位,蓝色为出口,白色为空地。

请问 n=2023n=2023 下最多能安排多少个停车位?

输出格式

一个正整数,表示你的答案。