数据结构 数据结构 ·在边框上添加四条线段 ◆使用一个M+1)N+1)*4的boo数组 即map||0-map叫N|0true,0≤I≤M Maplillil|dl-true,表示从d这个方向上有 mapo2|= mapI|2|true0≤I≤N 线经过点(i,j 8×4 数三角形的办法 数三角形的办法 分别数出每一种三角形的个数 ◆在向后寻找另外两个顶点的时候如果存 翘的户角形先个竞它封为商 在如图所示的线中的任意一条则停止 个顶点 MapLx,Ity ][1] Il (x1,y1) Map[xa][y J [2] II Map[x,][y [3] Il Map [xo] yo1[0]=true Map[xzl [y2][o] II Maplxo]Lyo][2]=true Mapx2]y2t2】 Map [x] y,][3]=true Map[x,][y:][3] II Mapx, -1]y,][3] 数三角形的办法 数三角形的办法 如果停止的时候x1y1)与(x2y2)满足条件 ◆其他三角形的做法与第一种基本相同 mapx,lly, 1[2]&& mapx,-1|[y2 /3), y 找到一个符合题意的三角形否则所寻找 的三角形不存在 (x2-1,y2)(x2,y2)8 数据结构 Š 使用一个(M+1)*(N+1)*4的bool数组 Š Map[i][j][d]=true,表示从d这个方向上有 一条线经过点(i, j). 0 1 2 3 数据结构 Š 在边框上添加四条线段 Š 即 map[I][0][0]=map[I][N][0]=true,(0≤I≤M) map[0][I][2]=map[M][I][2]=true,(0≤I≤N) 8 × 4 数三角形的办法 Š 分别数出每一种三角形的个数 Š 例如数第三种三角形:先选一个点确定其为三角 形 的左顶点,然后逐步“摸索”着确定它的另外两 个顶点. (x1,y1) (x0,y0) (x2,y2) Map[x0][y0][0]=true Map[x0][y0][2]=true Map[x1][y1][3]=true 数三角形的办法 Š 在向后寻找另外两个顶点的时候,如果存 在如图所示的线中的任意一条,则停止. (x2,y2) (x0,y0) (x2-1,y2) ( Map[x0][y0][1] || Map[x0][y0][2] || Map[x0][y0][3] || Map[x2][y2][0] || Map[x2][y2][2] || Map[x2][y2][3] || Map[x2-1][y2][3] ) (x1,y1) 数三角形的办法 Š 如果停止的时候(x1,y1)与(x2,y2)满足条件 (map[x1][y1][2] && !map[x2-1][y2][3]),则 找到一个符合题意的三角形.否则所寻找 的三角形不存在. (x1,y1) (x0,y0) (x2,y2 (x ) 2-1,y2) 数三角形的办法 Š 其他三角形的做法与第一种基本相同