我必须读取一个文件，其中存储有汽车矩阵（ 1 = BlueCar，2 = RedCar，0 = Empty ）。

我需要 编写一种算法来 以这种方式 移动 矩阵 的汽车 ：

• 蓝色的 向下 移动;
• 红色的 向右移动 ;
• 有一个 转弯 ，所有蓝色的都在移动，而有一个转弯，所有红色的都在移动。

在读取文件之前，我不知道矩阵的大小以及它是密集的还是稀疏的，因此我必须实现 两个数据结构 （一个用于密集，一个用于稀疏）和两个算法。

我需要达到 最佳的时间和空间复杂度 。

由于未知的矩阵大小，我认为是将数据存储在堆上。

如果矩阵是 密集的 ，我想使用类似的东西：

short int** M = new short int*[m];
short int*  M_data = new short int[m*n];

for(int i=0; i< m; ++i) 
{
    M[i] = M_data + i * n;
}

通过这种结构，我可以分配连续的内存空间，并且使用进行访问也很简单M[i][j]。

现在的问题是要为 稀疏
情况选择的结构，我还必须考虑如何以最简单的方式通过算法移动汽车：例如，当我评估一辆汽车时，我需要轻松地找到下一个位置（向下或向右）有另一辆车，或者如果它是空的。

最初，我想定义从通用Car对象继承的BlueCar和RedCar对象。在此对象中，我可以保存矩阵坐标，然后将其放入：

std::vector<BluCar> sparseBlu;
std::vector<RedCar> sparseRed;

否则我可以做类似的事情：

vector< tuple< row, column, value >> sparseMatrix

但是，寻找下一个职位的问题仍然存在。

可能这不是最好的方法，那么如何有效地实现稀疏情况呢？（也为稀疏使用独特的结构）