BFS36分求助!!!互关
查看原帖
BFS36分求助!!!互关
495433
kyrie_lrving1992楼主2023/5/1 14:48
#include <bits/stdc++.h>
using namespace std;
int _n = 0;
char _map[1500][1500];
bool _p[1500][1500];
bool _vis[1500][1500];
int _head , _tail;
int _cnt = 0;
int _queue[15000000][2];
int _EX[4] = {0 , 0 , 1 , -1};
int _EY[4] = {1 , -1 , 0 , 0};
int _ans = 0;
int _head1 , _tail1;
int _queue1[15000000][2];
int _vis1[1500][1500];
void BFS(int x , int y){
	_head = 1 , _tail = 1;
    _queue[_head][0] = x;
    _queue[_head][1] = y;
    while(_head <= _tail){
        int CurX , CurY;
        for(int i = 0 ; i <= 3 ; i++){
			CurX = _queue[_head][0] + _EX[i];
            CurY = _queue[_head][1] + _EY[i];
            if(CurX >= 1 && CurX <= _n && CurY >= 1 && CurY <= _n && _map[CurX][CurY] == '#' && _vis[CurX][CurY] == false){
                _tail++;
                _vis[CurX][CurY] = true;
                _queue[_tail][0] = CurX;
                _queue[_tail][1] = CurY;
            }
        }
        _head++;
    }
}
void BFS1(int x , int y){
	_head1 = 1 , _tail1 = 1;
    _queue1[_head1][0] = x;
    _queue1[_head1][1] = y;
    while(_head1 <= _tail1){
        int CurX , CurY;
        for(int i = 0 ; i <= 3 ; i++){
			CurX = _queue1[_head1][0] + _EX[i];
            CurY = _queue1[_head1][1] + _EY[i];
            if(CurX >= 1 && CurX <= _n && CurY >= 1 && CurY <= _n && _map[CurX][CurY] == '#' && _vis1[CurX][CurY] == false){
                _tail1++;
                _vis1[CurX][CurY] = true;
                _queue1[_tail1][0] = CurX;
                _queue1[_tail1][1] = CurY;
            }
        }
        _head1++;
    }
}
int main(){
	cin >> _n;
	for(int i = 1 ; i <= _n ; i++){
		for(int j = 1 ; j <= _n ; j++){
			cin >> _map[i][j];
		}
	}
	for(int i = 1 ; i <= _n ; i++){
		for(int j = 1 ; j <= _n ; j++){
			if(_vis1[i][j] == false && _map[i][j] == '#'){
				_cnt++;
				BFS1(i , j);
			}
		}
	}
	for(int i = 1 ; i <= _n ; i++){
		for(int j = 1 ; j <= _n ; j++){
			if(_map[i][j] == '#' && _vis[i][j] == false){
				if(_map[i][j - 1] == '#' && _map[i][j + 1] == '#' && _map[i - 1][j] == '#' && _map[i + 1][j] == '#'){
					_p[i][j] = true;
				}
			}
		}
	}
	for(int i = 1 ; i <= _n ; i++){
		for(int j = 1 ; j <= _n ; j++){
			if(_p[i][j] == true){
				_map[i][j] = '#';
			}
			else{
			    _map[i][j] = '.';
			}
		}
	}
	for(int i = 1 ; i <= _n ; i++){
		for(int j = 1 ; j <= _n ; j++){
			if(_vis[i][j] == false && _map[i][j] == '#'){
				_ans++;
				BFS(i , j);
			}
		}
	}
	cout << _cnt - _ans;
	return 0;
}
2023/5/1 14:48
加载中...