cpp dfs+bfs
//海水向八个方向搜索,能搜到的岛屿都不在环内,每搜到一个岛屿,就找出属于它的连通块
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
using PII = pair<int,int>;
const int N = 55;
char g[N][N];
bool st[N][N];
int mp[N][N];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int ddx[8] = {1,0,-1,0,1,1,-1,-1};
int ddy[8] = {0,1,0,-1,1,-1,1,-1};
int n,m;
int cnt;
void bfs(int x,int y) {
cnt++;
st[x][y] = true;
queue<PII> q;
q.push({x,y});
while(q.size()) {
auto t = q.front();q.pop();
for(int i=0;i<4;i++) {
int tx = t.first + dx[i];
int ty = t.second + dy[i];
if(tx<1 || tx>n || ty<1 || ty>m || st[tx][ty] || mp[tx][ty] != 1) continue;
else {
st[tx][ty] = true;
q.push({tx,ty});
}
}
}
}
void dfs(int x,int y) {
st[x][y] = true;
for(int i=0;i<8;i++) {
int tx = x+ddx[i];
int ty = y+ddy[i];
if(tx<0 || tx>n+1 || ty<0 ||ty>m+1 || st[tx][ty]) continue;
if(mp[tx][ty] == 1) bfs(tx,ty);
else dfs(tx,ty);
}
}
int main(){
int T;
cin>>T;
while(T--){
cnt = 0;
cin>>n>>m;
memset(st,0,sizeof st);
memset(mp,0,sizeof mp);
for(int i=1;i<=n;i++) cin>>g[i]+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
if(g[i][j] == '0') mp[i][j] = 0;
else mp[i][j] = 1;
}
dfs(0,0);
cout<<cnt<<endl;
}
return 0;
}