感染法和广度优先搜索及时间复杂度分析 —— NC269999 小红走矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了感染法和广度优先搜索及时间复杂度分析 —— NC269999 小红走矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目来源：

牛客周赛 Round 36

题目如下：

题目小红走矩阵
小红来到了一个n∗m的矩阵，她初始站在左上角，每次行走可以按“上下左右”中的一个方向走一步，但必须走到和当前格子不同的字符，也不能走到矩阵外。
小红想知道，从左上角走到右下角最少需要走多少步？

输入

第一行输入两个正整数n,m，用空格隔开。代表矩阵的行数和列数。

接下来的n行，每行输入一个长度为m的、仅由小写字母组成的字符串，用来表示矩阵。

1≤n,m≤1000

输出

如果无法到达右下角，则输出-1。否则输出一个整数，代表行走的最小步数。

尝试：感染法：

将该问题视作图论中的连通性问题，周围四个字母若与被识别字母不同则说明这两个字母是连通的，则可以考虑考虑时间因素的感染法：

其图解如下：

小红走矩阵,宽度优先,矩阵,算法,c++

希望：对每个传染源，我们需要记录周围可以传播的被传染者作为下一次传播的传染源，不重不漏。

定义结构体点，同时为了使用unordered_set（不重不漏）,使用自定义哈希函数：

struct Point {
    int x, y;
    // 重载相等操作符，用于std::unordered_set的去重
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
    Point(int iptx,int ipty){
        x = iptx; y = ipty;
    }
};

// 自定义哈希函数，用于std::unordered_set的哈希计算
namespace std {
    template <>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            return hash<double>()(p.x) ^ hash<double>()(p.y);
        }
    };
}

然后利用传染源去检测被传染者，并将这一回合的被传染者作为下一次的传染源，利用布尔矩阵记录某个点是否被传染。

如果没有传染到任何一个单位，那么infecting赋值为false，停止模拟传染：

bool infecting = true;
int tick = 0;

void testInfect(Point point,vector<string> charmap,vector<vector<bool>>& bmap,unordered_set<Point>& nextSource){
	int mx = charmap.size()-1;
	int my = charmap[0].size()-1;
	int x = point.x;
	int y = point.y;
	vector<vector<int>> testpoint = {{x+1,y},{x,y+1},{x-1,y},{x,y-1}};
	for(vector<int> p : testpoint){
		if((0<=p[0] && p[0]<=mx) && (0<=p[1] && p[1]<=my) && (charmap[p[0]][p[1]]!=charmap[x][y]) && (bmap[p[0]][p[1]]==false)){
			bmap[p[0]][p[1]] = true;
			infecting = true;
            nextSource.insert(Point(p[0],p[1]));
		}
	}
}

void scan(vector<string> charmap,vector<vector<bool>>& bmap,unordered_set<Point>& source){
	infecting = false;
	int mx = charmap.size()-1;
	int my = charmap[0].size()-1;
    unordered_set<Point> nextSource;
    for(Point sourcepoint : source){
        int x = sourcepoint.x;
        int y = sourcepoint.y;
        testInfect({x,y},charmap,bmap,nextSource);
    }
	if(infecting){
		tick++;
        source = nextSource;
	}
}

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
bool infecting = true;
int tick = 0;

struct Point {
    int x, y;
    // 重载相等操作符，用于std::unordered_set的去重
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
    Point(int iptx,int ipty){
        x = iptx; y = ipty;
    }
};

// 自定义哈希函数，用于std::unordered_set的哈希计算
namespace std {
    template <>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            return hash<double>()(p.x) ^ hash<double>()(p.y);
        }
    };
}

void testInfect(Point point,vector<string> charmap,vector<vector<bool>>& bmap,unordered_set<Point>& nextSource){
	int mx = charmap.size()-1;
	int my = charmap[0].size()-1;
	int x = point.x;
	int y = point.y;
	vector<vector<int>> testpoint = {{x+1,y},{x,y+1},{x-1,y},{x,y-1}};
	for(vector<int> p : testpoint){
		if((0<=p[0] && p[0]<=mx) && (0<=p[1] && p[1]<=my) && (charmap[p[0]][p[1]]!=charmap[x][y]) && (bmap[p[0]][p[1]]==false)){
			bmap[p[0]][p[1]] = true;
			infecting = true;
            nextSource.insert(Point(p[0],p[1]));
		}
	}
}

void scan(vector<string> charmap,vector<vector<bool>>& bmap,unordered_set<Point>& source){
	infecting = false;
	int mx = charmap.size()-1;
	int my = charmap[0].size()-1;
    unordered_set<Point> nextSource;
    for(Point sourcepoint : source){
        int x = sourcepoint.x;
        int y = sourcepoint.y;
        testInfect({x,y},charmap,bmap,nextSource);
    }
	if(infecting){
		tick++;
        source = nextSource;
	}
}

int main(){
	int x,y;
	cin >> x >> y;
	vector<string> charmap(x);
	vector<vector<bool>> bmap(x,vector<bool>(y,false));
	bmap[0][0]=true;
	for(int i=0;i<x;i++){
		cin >> charmap[i];
	}
    unordered_set<Point> source;
    Point start = Point(0,0);
    source.insert(start);
	while(infecting){
		if(bmap[x-1][y-1]==true){
			cout << tick;
			return 0;
		}
		scan(charmap,bmap,source);
	}
	cout << -1;
	return 0;
}

过了一部分用例，剩下的用例超时了。。

时间复杂度分析：

主要组成部分

主函数 (main)
- 读取输入：，其中 x 是地图的行数。
- 初始化数据结构：，其中 y 是地图的列数。
scan 函数
- 遍历 source 集合，并对每个元素调用 testInfect 函数。
testInfect 函数
- 对每个源点，检查其上下左右四个方向是否可以感染新的点，并将可感染的点添加到下一轮的源点集合中。

时间复杂度分析

初始化复杂度
- 初始化地图和布尔矩阵的复杂度为。
感染过程复杂度
- 每次感染过程中，最坏情况下，每个格子都可能被作为源点处理一次，即每个格子都可能被遍历一次来尝试感染其周围的格子。
- 对于每个源点，testInfect 函数会检查其四个方向，是一个常数时间操作，即。
- 最坏情况下，整个地图上的每个点都至少被遍历一次作为源点，因此这部分的时间复杂度是。
哈希表操作复杂度
- 插入和查找操作通常是，在极端情况下（极端的哈希冲突）可能退化到，但这种情况很少见，特别是使用良好设计的哈希函数时。
- 在这个场景中，由于 unordered_set 中存储的元素数量最多与地图大小相同，即，因此这部分操作的平均情况可以认为是。

总结

初始化：
每轮感染：（每个点最多被处理一次）
哈希表操作：平均，不会显著影响总体时间复杂度

因此，总体时间复杂度是。这里假设感染过程会覆盖整个地图，即每个点至少被访问一次。实际的运行时间可能由于地图的具体内容和感染的起始位置而有所不同，但从理论上讲，这是对该算法时间复杂度的一个合理估计。

之后我参照题解，结合个人的代码习惯重新写了一遍新的算法：具体思路：

定义结构体point,记录点坐标信息和走到该点的最小步数：

const int INF = 0x3f3f3f3f;

struct point{
    int x,y,minstep;
    point(int iptx,int ipty){
        x=iptx;y=ipty;minstep=INF;
    }
};

构建广度优先搜索函数：当队列不为空，检测队首点是否能感染周围四个点：检测能感染的条件：

i.边界条件：检测的四个点不能超过边界。

ii.最小步数条件：周围点的最小步数大于从队首点最小步数+1。

一旦能感染，则将周围被感染的点加入队列末尾。无论是否能感染，都将队首元素弹出。

广度优先搜索代码如下：

void bfs(vector<string> charmap,vector<vector<point>>& pointmap){
    int mx=charmap.size()-1;
    int my=charmap[0].size()-1;
    queue<point> q;
    q.push(pointmap[0][0]);
    vector<int> dx = {1,-1,0,0}; vector<int> dy = {0,0,1,-1};
    while(q.size()){
        point cur = q.front();
        int cstep = cur.minstep+1;
        for(int i=0;i<4;i++){
            int x = cur.x;int y = cur.y;
            int cx = cur.x + dx[i];int cy=cur.y + dy[i];
            if(0<=cx && cx<=mx && 0<=cy && cy<=my && 
            charmap[x][y]!=charmap[cx][cy] &&
            (pointmap[cx][cy].minstep > cstep)){
                pointmap[cx][cy].minstep = cstep;
                q.push(pointmap[cx][cy]);
            }
        }
        q.pop();
    }
}

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

struct point{
    int x,y,minstep;
    point(int iptx,int ipty){
        x=iptx;y=ipty;minstep=INF;
    }
};

void bfs(vector<string> charmap,vector<vector<point>>& pointmap){
    int mx=charmap.size()-1;
    int my=charmap[0].size()-1;
    queue<point> q;
    q.push(pointmap[0][0]);
    vector<int> dx = {1,-1,0,0}; vector<int> dy = {0,0,1,-1};
    while(q.size()){
        point cur = q.front();
        int cstep = cur.minstep+1;
        for(int i=0;i<4;i++){
            int x = cur.x;int y = cur.y;
            int cx = cur.x + dx[i];int cy=cur.y + dy[i];
            if(0<=cx && cx<=mx && 0<=cy && cy<=my && 
            charmap[x][y]!=charmap[cx][cy] &&
            (pointmap[cx][cy].minstep > cstep)){
                pointmap[cx][cy].minstep = cstep;
                q.push(pointmap[cx][cy]);
            }
        }
        q.pop();
    }
}

int main(){
    int x,y;
    cin >> x >> y;
    vector<string> charmap(x);
    for(int i=0;i<x;i++){
        cin >> charmap[i];
    }
    vector<vector<point>> pointmap(x,vector<point>(y,point(0,0)));
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            pointmap[i][j]=point(i,j);
        }
    }
    pointmap[0][0].minstep=0;
    bfs(charmap,pointmap);
    if(pointmap[x-1][y-1].minstep==INF){
        cout << -1;
        return 0;
    }
    else{
        cout << pointmap[x-1][y-1].minstep;
        return 0;
    }
}

这段代码能全过，时间复杂度分析如下：

主要组成部分

主函数 (main)
- 读取输入：，其中 x 是地图的行数。
- 初始化 pointmap：，其中 y 是地图的列数。
bfs 函数
- 广度优先搜索过程，每个点最多被访问一次。

时间复杂度分析

初始化复杂度
- 初始化 charmap 和 pointmap 的复杂度为。
广度优先搜索复杂度 (bfs)
- 在 BFS 中，每个点至多入队一次，并且出队后检查其四个方向的邻居。对于每个点，检查和更新四个方向的操作是常数时间的，即。
- 因此，对于整个地图上的个点，总的时间复杂度为。