罗湖做网站多少钱,如何在百度上发布广告,心理医生免费咨询,石家庄建站系统样例#xff1a; 解法#xff1a;
1.遍历矩阵
2.判断矩阵[i][j]#xff0c;若是未标记细胞则遍历相邻所有未标记细胞并标记#xff0c;且计数
实现#xff1a;遍历相邻所有未标记细胞
以DFS实现#xff1a;
function dfs(当前状态) {if (终止条件) {}vis[标记当前状…
样例 解法
1.遍历矩阵
2.判断矩阵[i][j]若是未标记细胞则遍历相邻所有未标记细胞并标记且计数
实现遍历相邻所有未标记细胞
以DFS实现
function dfs(当前状态) {if (终止条件) {}vis[标记当前状态]for (寻找新状态) {if (状态合法) {dfs(新状态)//看情况是否需要重置vis[]}}
}
代码
#includeiostream
#includevector
using namespace std;
int dir[4][2] { 0,1,1,0,-1,0,0,-1 };
void dfs(vectorvectorint a, int x, int y) {if (a[x][y] 0) return;a[x][y] 0;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx a.size() || nexty 0 || nexty a[0].size()) {continue;}if (a[nextx][nexty] ! 0) {dfs(a, nextx, nexty);}}
}
int main() {int m, n;cin m n;vectorvectorint a(m, vectorint(n , 0));for (int i 0; i m; i)for (int j 0; j n; j)cin a[i][j];int result 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (a[i][j] ! 0) {result;dfs(a, i, j);}}}cout result;return 0;
}
以BFS实现
function bfs(当前节点) {当前节点入列标记当前节点while (队列不为空) {当前节点出列寻找合法相邻节点合法相邻节点入列标记相邻节点}
}
代码
#includeiostream
#includevector
#includequeue
#includeutility
using namespace std;
int dir[4][2] { 0,1,1,0,-1,0,0,-1 };
void bfs(vectorvectorint a, int x, int y) {queuepairint, int que;que.push({ x,y });a[x][y] 0;while (!que.empty()) {pairint, int cur que.front();que.pop();int curx cur.first;int cury cur.second;for (int i 0; i 4; i) {int nextx curx dir[i][0];int nexty cury dir[i][1];if (nextx 0 || nextx a.size() || nexty 0 || nexty a[0].size()) {continue;}if (a[nextx][nexty] ! 0) {que.push({ nextx,nexty });a[nextx][nexty] 0;}}}
}
int main() {int m, n;cin m n;vectorvectorint a(m, vectorint(n, 0));for (int i 0; i m; i)for (int j 0; j n; j)cin a[i][j];int result 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (a[i][j] ! 0) {result;bfs(a, i, j);}}}cout result;return 0;
}
