俄罗斯方块转弯算法实现

关于俄罗斯方块程序对战程序中实现方块转弯的算法描述。

为了方便描述算法的原理,以方块的左上角为基准,简化问题为一个11的小方块,在rowcol的矩阵中可以最终移动到哪个位置。

现在来看看位置(x y)是否可以移动到(即使是临时的)。 如果它可以被移动到,那么它从哪个位置移动过来。也很简单。 首先,如果上面位置(x-1 y)可以被移动到,那么(x y)也是可以的。 其次,如果左边(x y-1)或右边(x y+1)的位置可以被移动到,那么(x y)也是可以的。

那么评估位置是否可以移动到(即使是临时的)的算法,就可以这么描述:

1.定义一个二维数组,表示某个格是否移动到(即使是临时的),默认为false不可以。
2.初始化第一行的状态,如果方块在(0 i)可放置(和当前矩阵没冲突)则设置state[0][i]为true。
3.从第二行开始遍历,针对每一行i进行以下处理
3.1.对当前行的列j进行遍历,如果当前位置可放置,且同一列上一行的位置可移动到,则state[i][j]为true
3.2.对当前行的列j进行遍历,如果当前位置state[i][j]为true,则往左边(右边)一直检查
3.3.如果左边位置k可放置,则state[i][k]为true,直到k不可放置或k位置已经为true

最后,通过检查state就可以直到哪个位置可以被移动到。判断这个位置是否是最终移动的位置,则可以判断该位置是否最后一行,或同一列的下一个位置是否可以放置。

不过这里还有个问题,就是即使知道某个位置是可以被移动到的,但怎么还原出下落的路线呢?

其实,我们可以记住拐点,就可以知道路线了。 现在我们在(4,3)位置记录上一个拐点(3,3),然后在(3,3)记录再上一个拐点(3,2),以此类推就可以得到下落路线(反向的)。 我们想要的结果是

(0,0)(+,+)(+,+)(+,+)(+,+)
(0,0)(1,0)(1,0)(+,+)(+,+)
(+,+)(+,+)(1,2)(+,+)(+,+)
(+,+)(+,+)(1,2)(3,2)(+,+)
(+,+)(+,+)(+,+)(3,3)(+,+)

具体怎么记录这个拐点呢?可以在上面的算法基础上修改一下即可。 首先,考虑把(x,y)这个拐点值记录为x*ROW+y,这样修改state为整形二维数组。

1.定义一个二维数组,表示某个格是否移动到(即使是临时的),默认为MAX(ROW*COL,一个不可能的拐点),表示不可以。
2.初始化第一行的状态,如果方块在(0 i)可放置(和当前矩阵没冲突)则设置state[0][i]为拐点(0,i),即j。
3.从第二行开始遍历,针对每一行i进行以下处理
3.1.对当前行的列j进行遍历,如果当前位置可放置,且同一列上一行的位置不为MAX,则state[i][j]为state[i-1][j]
3.2.对当前行的列j进行遍历,如果当前位置state[i][j]不为MAX,则往左边(右边)一直检查
3.3.如果左边位置k可放置,则state[i][k]为拐点(i,j),即i*COL+j,直到k不可放置或k位置不为MAX