痛苦地debug,仍然WA
查看原帖
痛苦地debug,仍然WA
385781
guanjinquan楼主2021/7/14 13:14

## 求聚聚们看看我的思路吧

定义maze存下地图,cnt记录交点的数量,du记录一个点有多少个方格有交点,ans记录答案(1:/ , 2:\)

(1)0~n行,0~n列,每个点定义一个du[i][j]数组作为该点被考虑了多少次,顶点du为1,边界为2,内部为4

减枝:

       ①当度数小于(地图要求数量-cnt已有数量)时,可以直接减枝

        ②当度数为0时,这个时候就可以 判断一个点的正确性

【验证正确性我写了一个check函数来check每一个点(0~n * 0~n)的正确性】

(2)看到题解中有个大佬说可以提前预处理出那些满度数或者度数等于地图要求数的点,然后写了一个initAns函数

       ①如果maze[i][j]-cnt[i][j]==0,那么说明这个这个点已经满交了,其他格子可以推出,与这个点没有交点

       ②如果maze[i][j]-cnt[i][j]==du[i][j],du[i][j]>0,那么说明其它格子一定都与这个点有交点,所以可以预处理。

(3)关于判环的问题,我并没有使用并查集,如果一个点的du[i][j]==4,它在地图内部,若cnt[i][j]==0(即周围四个格子都与他没有交点),那必然有环

等码力足够了,就回来继续debug

2021/7/14 13:14
加载中...