密集和稀疏矩阵的高效(时间和空间复杂度)数据结构

我必须读取一个文件,其中存储了一个带有汽车的矩阵(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 sparseBlu;
std::vector sparseRed;

否则我可以这样做:

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

但是仍然存在找到下一个位置的问题.

可能这不是最好的方法,所以如何以有效的方式实现稀疏案例呢？(也使用稀疏的独特结构)