题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
bfs版
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define x1 first
#define x2 second
using namespace std;
typedef pair<int, int> PII;
int T, n, m,op; char g[107][107];bool st[107][107];
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
void bfs(int x, int y)
{
queue<PII> q;
q.push({x,y});
st[x][y] = 1;
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int a = t.x1 + dx[i]; int b = t.x2 + dy[i];
if (a>=0&&a<n&&b>=0&&b<m&&(g[a][b]=='1')&&!st[a][b]) {
st[a][b] = 1; q.push({ a,b });
}
}
}
}
int query()
{
memset(st, 0, sizeof(st));
int res = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (g[i][j] == '1' && !st[i][j]) {
res++; bfs(i,j);
}
}
}
return res;
}
int main(int argc, char* argv[])
{
cin >> T;
for (int k = 1; k <= T; k++)
{
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
cin >> op;
bool is_cout = 0;
for (int i = 0; i < op; i++)
{
char c;
cin >> c;
if (c == 'Q') {
if (is_cout == 0) printf("Case #%d:\n",k), is_cout = 1;
cout << query() << endl;
}
else {
int x, y, z;
cin >> x >> y >> z;
if (z == 1) g[x][y] = '1';
else g[x][y] = '0';
}
}
}
return 0;
}
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla