数学（四）

flood fill能够在线性时间复杂度内，找到某个点所在的连通块。

四联通常用数组加一层循环判断

int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

八联通常用二层循环遍历‬

tip:注意二层循环排除自己的情况

for (int i = t.x - 1; i ＜= t.x + 1; i ++ )

for (int j = t.y - 1; j ＜= t.y + 1; j ++ )

注意循环条件内的if特判，参考代码如下（应该是acwing1098）

include：＜iostream＞

include：＜queue＞

include：＜utility＞

using namespace std;

define：x first

define：y second

define：IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

typedef pair＜int,int＞ PII;

const int N=55;

queue＜PII＞q;

int g[N][N];

bool st[N][N];

int cnt=0, ss=0, n, m;

int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

int bfs(int a, int b) {

q.push({a, b});

st[a][b]=true;

int area=0;

while(q.size()) {

auto t=ont();

q.pop();

area++;

for(int i=0; i＜4; i++) {

int sx=t.x+dx[i], sy=t.y+dy[i];

if(sx＜=0 || sy＜=0 || sx＞n || sy＞m) continue;

if(g[t.x][t.y] ＞＞ i & 1) continue;

if(st[sx][sy]) continue;

q.push({sx, sy});

st[sx][sy]=true;

}

}

return area;

}

void solve() {

cin＞＞n＞＞m;

for(int i=1; i＜=n; i++) {

for(int j=1; j＜=m; j++) {

cin＞＞g[i][j];

}

}

for(int i=1; i＜=n; i++) {

for(int j=1; j＜=m; j++) {

if(!st[i][j]) {

ss=max(ss, bfs(i, j));

cnt++;

}

}

}

cout<

cout<

}

int main() {

IOS;

int t=1;

while(t--) {

solve();

}

return 0;

}