题目描述
flood fill 联通块
深搜(用了辅助标记数组)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int T, r, c;
int z;
char g[N][N];
int t[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
void dfs(int x, int y)
{
t[x][y] = 1;
for (int i=0; i<4; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < r && b >= 0 && b < c && g[a][b] == '1' && !t[a][b])
dfs(a, b);
}
}
int query()
{
memset(t, 0, sizeof(t));
int cnt = 0;
for (int i=0; i<r; i++)
for (int j=0; j<c; j++)
if (g[i][j] == '1' && !t[i][j])
{
cnt++;
dfs(i, j);
}
return cnt;
}
int main()
{
cin >> T;
for (int k=1; k<=T; k++)
{
cin >> r >> c;
for (int i=0; i<r; i++)
for (int j=0; j<c; j++)
cin >> g[i][j];
printf("Case #%d:\n", k);
cin >> z;
for (int i=1; i<=z; i++)
{
char opt;
cin >> opt;
switch(opt)
{
case 'Q':
cout << query() << endl;
break;
case 'M':
int aa, bb;
char cc;
cin >> aa >> bb >> cc;
g[aa][bb] = cc;
break;
default:
break;
}
}
}
return 0;
}
广搜
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int T, r, c;
int z;
char g[N][N];
int t[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
void bfs(int x, int y)
{
queue<PII> q;
q.push({x, y});
t[x][y] = 1;
while (!q.empty())
{
auto k = q.front();
q.pop();
for (int i=0; i<4; i++)
{
int a = k.x + dx[i], b = k.y + dy[i];
if (a >= 0 && a < r && b >= 0 && b < c && g[a][b] == '1' && !t[a][b])
{
q.push({a, b});
t[a][b] = 1;
}
}
}
}
int query()
{
memset(t, 0, sizeof(t));
int cnt = 0;
for (int i=0; i<r; i++)
{
for (int j=0; j<c; j++)
{
if (g[i][j] == '1' && t[i][j] == 0)
{
bfs(i, j);
cnt ++;
}
}
}
return cnt;
}
int main()
{
cin >> T;
for (int k=1; k<=T; k++)
{
cin >> r >> c;
for (int i=0; i<r; i++)
for (int j=0; j<c; j++)
cin >> g[i][j];
printf("Case #%d:\n", k);
cin >> z;
for (int i=1; i<=z; i++)
{
char opt;
cin >> opt;
switch(opt)
{
case 'Q':
cout << query() << endl;
break;
case 'M':
int aa, bb;
char cc;
cin >> aa >> bb >> cc;
g[aa][bb] = cc;
break;
default:
break;
}
}
}
return 0;
}