BFS求助
查看原帖
BFS求助
1067386
beiyu123楼主2024/3/29 12:31

只能过前三个点,第四个点我自己测输出的明明是五,但洛谷说是四

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,vis[105][105],mp[105][105],ans = 0;
struct pp {
	int x,y;
};
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
queue<pp> que;
void bfs(int x,int y) {
	pp st;
	st.x = x,st.y = y;
	vis[x][y] = 1;
	que.push(st);//起点放在队首,作为第一步
	while(!que.empty()) {
		pp now = que.front();
		for(int i = 0; i < 4; i++) {
			pp next=now;
			next.x += dir[i][0];
			next.y += dir[i][1];
			if(mp[next.x][next.y] && !vis[next.x][next.y]) {
				vis[next.x][next.y] = 1;
				que.push(next);
			}
		}
		que.pop();
	}
}
int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%1d",&mp[i][j]);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(mp[i][j] && !vis[i][j]) {
				bfs(i,j);
				ans++;
			}
		}
	}
	cout << ans;
	return 0;
}

第四个点输入: 4 10 0230500067 1004560500 2045600671 0000000089 输出:5

2024/3/29 12:31
加载中...