腾讯音乐娱乐笔试真题&求职宝典理工科版

1.3.1 三国鼎立

【题目描述】

在n∗m的棋盘格状土地上盘踞着三个国家的若干股势力，上下左右相邻的属于同一个国家的土地被认为是同一股势力。现在想知道，土地上总共有多少股势力？

输入描述：

第一行两个正整数，土地宽n，长m；

接下来一个n∗m个矩阵，今包含'1'、'2'、'3'，表示土地上的国家分布。

输出描述：

一个正整数，势力股数。

备注：

1≤n、w≤100。

输入样例：

4 4

1122

1222

3111

3333

输出样例：

4

说明：

11

1

是1国的一块势力

22

222

是2国一块势力

3

3333

是3国一块势力

111

是1国的另一块势力

总共4块势力

【解题思路】

经典连通块搜索问题，枚举每个点出发往各个方向搜索相连通的位置。

【参考代码】

#include <bits/stdc++.h>

using namespace std;

void dfs(vector<vector<int>> &a, int x, int y, int val) {

if (a[x][y] != val)

return;

a[x][y] = 0;

if (x + 1 < a.size())

dfs(a, x + 1, y, val);

if (y + 1 < a[0].size())

dfs(a, x, y + 1, val);

if (x - 1 >= 0)

dfs(a, x - 1, y, val);

if (y - 1 >= 0)

dfs(a, x, y - 1, val);

}

int main() {

ios::sync_with_stdio(0), cin.tie(0);

int n, m;

cin >> n >> m;

vector<vector<int>> a(n, vector<int>(m));

for (int i = 0; i < n; ++i) {

string line;

cin >> line;

for (int j = 0; j < m; ++j)

a[i][j] = line[j] - '0';

}

int res = 0;

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j) {

if (a[i][j] == 0)

continue;

++res;

dfs(a, i, j, a[i][j]);

}

cout << res << endl;

return 0;

}

......

资料全部内容请看《2025届求职宝典-理工科版》

不收费，2人组团即可免费领取！已经发出10000份，涵盖各大公司求职资料，助你事半功倍！

资料包含：

• 30+大厂面试真题+解析
• 软件方向：阿里、腾讯、百度、小米、华为、美团......
• 硬件方向：华为、比亚迪、汇川、新华三、中兴、海康威视......
• 机械方向：比亚迪、华为、美的、长江存储、宁德时代......
• 30+大厂岗位薪资爆料
• 30+大厂offer攻略

拿offer，别犹豫，点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-tiezi11

电脑端请微信扫码>>

多说无益，直接上资料截图

每个方向专栏售价69元，但是参与2人组团就可免费领取！

点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-tiezi11