企业网站作业怎么做,长沙做一个网站要多少钱,注册公司代理费用标准,鞍山市城市建设网站解题思路#xff1a; 这是大佬的思路#xff1a; 这道题可能上来会想到搜格子#xff0c;但搜格子意味着更高的复杂度以及判连通的需要#xff0c;本题似乎搜索要切开的边更优。由题意#xff0c;这一条切割线必定经过图的中心点#xff0c;那么我们一旦确定了半条到达边…
解题思路 这是大佬的思路 这道题可能上来会想到搜格子但搜格子意味着更高的复杂度以及判连通的需要本题似乎搜索要切开的边更优。由题意这一条切割线必定经过图的中心点那么我们一旦确定了半条到达边界的分割线就能根据这半条对称画出另外半条。而由于结果中心对称性搜索出来的个数应该除以4得出最终结论。在搜索过程中需要注意的是我们搜索出的半条分割线不能同时经过关于中心对称的两个点所以在标记时需要将对称的点也标上。” 中心点是(3,3)从3,3出发向右、向左、向上、向下四个方向DFS即可。 思路转载地址 https://blog.csdn.net/weixin_43914593/article/details/112257103
这个图能让大家更好的理解大佬的思路。 终止条件 我们会发现当这条线碰到边界的时候就能构成一种情况因此终止条件为
if (x 0 || y 0 || x 6 || y 6)注意: 这两行代码很关键!!!
st[3][3] true;
cnt / 4 代码如下
#include iostream
using namespace std;
const int N 10;
bool st[N][N];
int cnt;int dx[] {0, 0, 1, -1}, dy[] {1, -1, 0, 0};void dfs(int x, int y) {if (x 0 || y 0 || x 6 || y 6) {cnt;return ;}for (int i 0; i 4; i) {int xx x dx[i], yy y dy[i];if (!st[xx][yy]) {st[xx][yy] true;st[6 - xx][6 - yy] true;//对称点也要标记哦dfs(xx, yy);st[xx][yy] false;st[6 - xx][6 - yy] false;}xx xx - dx[i], yy yy - dy[i];//可有可无有更规范}
}int main() {st[3][3] true;//这一步很关键!!!dfs(3, 3);cout cnt / 4 endl;//记得除以4哦return 0;
}
