俄罗斯方块转弯算法实现

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

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

现在来看看位置(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