此问题涉及在邻接矩阵上操作的深度优先搜索的边。
给定邻接矩阵:
{1,0,0,1},
{1,1,0,0},
{0,0,0,1},
{1,1,1,1}
我有一个运行良好的DFS,如下所示:
typedef std::vector<std::vector<short>> matrix;
void myClass::dfs(short row, short column, std::shared_ptr<matrix> m_visited, const matrix &sky) {
if (m_visited->at(row).at(column) == 1) {
return;
}
m_visited->at(row).at(column) = 1; //Mark the node as visited
if(row+1 <= sky.size()-1 && sky.at(row+1).at(column) == 1) { //Look horizontally forward
dfs(row+1, column, m_visited, sky);
}
if(row-1 >= 0 && sky.at(row-1).at(column) == 1) { //Look horizontally backward
dfs(row-1, column, m_visited, sky);
}
if(column+1 <= sky.at(0).size()-1 && sky.at(row).at(column+1) == 1) { //Look vertically down
dfs(row, column+1, m_visited, sky);
}
if(column-1 >= 0 && sky.at(row).at(column-1) == 1) { //Look vertically up
dfs(row, column-1, m_visited, sky);
}
}
现在,我被赋予了替换std::vector
带有std::unordered_set
我的问题:size_t
是无符号的,因此,例如,当行=0
(其中行的类型为size_t
)时,行-1
未定义,并且(行-1>0)
在编译器上的计算结果为true。
如何使用size_t
测试行-1
是否仍在邻接矩阵的边界内?
这是一个简单的数学问题:行-1>; 0<=>; 行>; lt;1
和列-1> 0<=>; 列>; 0
。 您可以替换
if(row-1 >= 0 && sky.at(row-1).at(column) == 1)
与
if(row >= 1 && sky.at(row-1).at(column) == 1)
和
if(column-1 >= 0 && sky.at(row).at(column-1) == 1)
与
if(column >= 1 && sky.at(row).at(column-1) == 1)
您还应该考虑替换
if(row+1 <= sky.size()-1 && sky.at(row+1).at(column) == 1)
与
if(sky.size() >= 2 && row <= sky.size()-2 && sky.at(row+1).at(column) == 1)
和
if(column+1 <= sky.at(0).size()-1 && sky.at(row).at(column+1) == 1)
与
if(sky.at(row).size() >= 2 && column <= sky.at(row).size()-2 && sky.at(row).at(column+1) == 1)
避免各种溢出和下溢。