bfs 求助,样例全过,自认为码风优良
查看原帖
bfs 求助,样例全过,自认为码风优良
938449
xiaoming007楼主2023/6/11 15:10
#include <iostream>
#include <vector>
using namespace std;
struct Queue{
	struct node{
		int x, y;
	}; 
	node u[1010100];
	int head = 1, tail = 0;
	inline void reuse(){
		head = 1, tail = 0;
	}
	inline void push(node a){
		u[++tail] = a;
	}
	inline void pop(){
		++head;
	}
	inline node front(){
		return u[head];
	}
	inline node back(){
		return u[tail];
	}
	inline int size(){
		return tail - head + 1;
	}
	inline bool empty(){
		return tail < head;
	}
}q;
int n, m;
vector<vector<int>> dir(4, vector<int>(2));
int main(){
	auto init = []{
		dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	};
	init();
	scanf("%d%d", &n, &m);
	vector<vector<char>> a(n+1, vector<char>(m+1, 'X'));
	vector<vector<bool>> vis(n+1, vector<bool>(m+1, 0));
	vector<vector<int>> be(n+1, vector<int>(m+1, 1));
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) cin >> a[i][j];
	auto in = [](int x, int y) -> bool{
		return (x >= 0 && y >= 0 && x <= n && y <= m);
	};
	q.reuse();
	q.push({0, 0});
	while(!q.empty()){
		Queue::node frt = q.front();
		q.pop();
		if(a[frt.x][frt.y] == '0'){
			be[frt.x][frt.y] = 0;
		}
		for(int i = 0; i < 4; ++i){
			int x = frt.x + dir[i][0], y = frt.y + dir[i][1];
			if(in(x, y) && vis[x][y] == 0 && a[x][y] != '*'){
				q.push({x, y});
				vis[x][y] = 1;
			}
		}
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) cnt += be[i][j] && a[i][j] == '0';
	printf("%d\n", cnt);
	return 0;
}
2023/6/11 15:10
加载中...