TIOJ 1081 . B.影像辨識

胡亂BFS

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
bool vis[1001][1001];
bool tab[1001][1001];
int quex[2000000], quey[2000000];
int main()
{
 int n,m;
 for(;;){
  scanf("%d %d", &n, &m);
  if(n+m == 0) break;
  char str[1011];
  for(int lx = 0;lx < n;lx++){
   scanf("%s", str);
   for(int ly = 0;ly < m;ly++)
    tab[lx][ly] = str[ly]=='1';
  }
  memset(vis, 0, sizeof(vis));
  int cnt = 0;
  for(int lx = 0;lx < n;lx++){
   for(int ly = 0;ly < m;ly++){
    if(vis[lx][ly]) continue;
    if(not tab[lx][ly]) continue;
    int st = 0, ed = 1;
    quex[st] = lx, quey[st] = ly;
    cnt++;
    vis[lx][ly] = true;
    while(st < ed){
     int px = quex[st], py = quey[st]; st++;
     if(px-1 >= 0 and tab[px-1][py] and not vis[px-1][py])
      {vis[px-1][py] = true, quex[ed] = px-1, quey[ed] = py; ed++;}
     if(px+1 < n and tab[px+1][py] and not vis[px+1][py])
      {vis[px+1][py] = true, quex[ed] = px+1, quey[ed] = py; ed++;}
     if(py-1 >= 0 and tab[px][py-1] and not vis[px][py-1])
      {vis[px][py-1] = true, quex[ed] = px, quey[ed] = py-1; ed++;}
     if(py+1 < m and tab[px][py+1] and not vis[px][py+1])
      {vis[px][py+1] = true, quex[ed] = px, quey[ed] = py+1; ed++;}
     if(px+1 < n and py+1 < m and tab[px+1][py+1] and not vis[px+1][py+1])
      {vis[px+1][py+1] = true, quex[ed] = px+1, quey[ed] = py+1; ed++;}
     if(px+1 < n and py-1 >= 0 and tab[px+1][py-1] and not vis[px+1][py-1])
      {vis[px+1][py-1] = true, quex[ed] = px+1, quey[ed] = py-1; ed++;}
     if(px-1 >= 0 and py+1 < m and tab[px-1][py+1] and not vis[px-1][py+1])
      {vis[px-1][py+1] = true, quex[ed] = px-1, quey[ed] = py+1; ed++;}
     if(px-1 >= 0 and py-1 >= 0 and tab[px-1][py-1] and not vis[px-1][py-1])
      {vis[px-1][py-1] = true, quex[ed] = px-1, quey[ed] = py-1; ed++;}
    }
   }
  }
  printf("%d\n",cnt);
 }
 return 0;
}