Go: // AOJ 1160: How Many Islands? http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160

package main

import (
	"bufio"
	"container/list"
	"fmt"
	"os"
	"strconv"
)

var SEA = 0
var LAND = 1

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

func discoverIslands(M, V [][]int, H, W int) int {
	// 島を探す
	queue := list.New()
	islands := 0
	for i := 1; i <= H; i++ {
		for j := 1; j <= W; j++ {
			// 訪問済みの土地ならスキップ
			if V[i][j] == 1 {
				continue
			}

			// 訪問中の土地が海なら訪問済みにしてスキップ
			if M[i][j] == SEA {
				V[i][j] = 1
				continue
			}

			// 未訪問の陸地が見つかったので
			// 島の数を1つ増やし、この陸地から辿れる陸地を訪問していく
			islands++
			queue.PushBack([]int{i, j})

			for queue.Len() > 0 {
				cur := queue.Remove(queue.Front()).([]int)
				h, w := cur[0], cur[1]
				if V[h][w] == 1 {
					continue
				}
				V[h][w] = 1

				// 全方向に未訪問の陸地がないか探索
				for v := -1; v <= 1; v++ {
					for l := -1; l <= 1; l++ {
						dh := h + v
						dw := w + l
						if M[dh][dw] == LAND && V[dh][dw] == 0 {
							queue.PushBack([]int{dh, dw})
						}
					}
				}
				/*
					if M[h-1][w] == LAND {
						queue.PushBack([]int{h - 1, w})
					}
					if M[h-1][w+1] == LAND {
						queue.PushBack([]int{h - 1, w + 1})
					}
					if M[h][w+1] == LAND {
						queue.PushBack([]int{h, w + 1})
					}
					if M[h+1][w+1] == LAND {
						queue.PushBack([]int{h + 1, w + 1})
					}
					if M[h+1][w] == LAND {
						queue.PushBack([]int{h + 1, w})
					}
					if M[h+1][w-1] == LAND {
						queue.PushBack([]int{h + 1, w - 1})
					}
					if M[h][w-1] == LAND {
						queue.PushBack([]int{h, w - 1})
					}
					if M[h-1][w-1] == LAND {
						queue.PushBack([]int{h - 1, w - 1})
					}
				*/
			}
		}
	}
	return islands
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	for {
		W, H := nextInt(sc), nextInt(sc)

		if W == 0 && H == 0 {
			break
		}
		// Initialize map and visted list
		M := make([][]int, H+2)
		V := make([][]int, H+2)
		for i := 0; i < H+2; i++ {
			M[i] = make([]int, W+2)
			V[i] = make([]int, W+2)
		}
		for i := 1; i <= H; i++ {
			for j := 1; j <= W; j++ {
				M[i][j] = nextInt(sc)
			}
		}

		islands := discoverIslands(M, V, H, W)

		fmt.Println(islands)
	}
}

C++: #include<iostream>
#include<vector>
using namespace std;

int main() {
	int n;
	while (cin >> n, n) {

		vector<vector<int>>list(n, vector<int>(n, -1));
		int number;

		for (int i = 0;i < n;i++) {
			cin >> number;
			for (int j = 0;j < number;j++) {
				int codename;
				cin >> codename;
				list[i][codename - 1] = 1;
			}
		}//list[a][b]:a know b

		cin >> number;
		
		vector<int>ans(n,1);
		int leaked;
		for (int i = 0;i < number;i++) {
			cin >> leaked;
			for (int j = 0;j < n;j++) {
				if (list[j][leaked - 1] <= 0) ans[j] = 0;
			}
		}//who is imposible
		int sum = 0,telltale;

		for (int i = 0;i < n;i++) {
			sum += ans[i];
			if (ans[i] == 1) telltale = i + 1;
		}

		if (sum == 1)cout << telltale << endl;
		else cout << -1 << endl;

	}
	return 0;
}

C++: #include<iostream>
#define N 51
using namespace std;

int w, h, ans = 0, map[N][N];

void search_zahyou(int w, int h);

int main(){
	while(cin >>w >>h){
		ans = 0;
		if(w == 0 && h == 0) break;
		for(int i = 0; i < h; i++){
			for(int k = 0; k < w; k++){
				cin >>map[i][k];
			}
		}
		for(int i = 0; i < h; i++){
			for(int k = 0; k < w; k++){
				if(map[i][k] == 0){
					continue;
				}
				else{
					ans++;
					search_zahyou(i, k);
				}
			}
		}
		cout <<ans <<endl;
	}
	return 0;
}

void search_zahyou(int inh, int inw){
	int searchh[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, searchw[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
	if(h <= inh || w <= inw || h < 0 || w < 0){
	} else{
		map[inh][inw] = 0;
		for(int i = 0; i < 8; i++){
			if(map[inh + searchh[i]][inw + searchw[i]] == 1){
				search_zahyou(inh + searchh[i], inw + searchw[i]);
			}
		}
	}
}

C++: #include <iostream>
#include <stack>
using namespace std;

int map[100][100];
int w=0,h=0;

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

void dfs(int x,int y);

int main(){
  while(1){
    cin>>w>>h;

    if(w==0&&h==0)
      break;

    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cin>>map[i][j];
      }
    }

    int result=0;

    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(map[i][j]==1){
	  result++;
	  dfs(j,i);
	}
      }
    }
    cout<<result<<endl;
  }
    
  return 0;
}

void dfs(int x,int y){
  map[y][x]=0;
  for(int i=0;i<8;i++){
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(nx>=0&&nx<w&&ny>=0&&ny<h&&map[ny][nx]==1){
      dfs(nx,ny);
    }
  }
}

C++: #include <stdio.h>
int map[100][100],n,m;
bool went[100][100];
void walk(int x,int y){
    if(x<0||y<0||x>=n||y>=m)return ;
    if(went[x][y])return ;
    if(map[x][y]==0)return ;
    went[x][y]=true;
    walk(x-1,y);
    walk(x+1,y);
    walk(x,y+1);
    walk(x,y-1);
    walk(x+1,y+1);
    walk(x+1,y-1);
    walk(x-1,y+1);
    walk(x-1,y-1);
    return ;
}
int main(){
    int ans;
    while(1){
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)return 0;
        ans=0;
        for(int i=0;i<n;i++)for(int j=0;j<m;j++){
            scanf("%d",&map[i][j]);
            went[i][j]=false;
        }
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(!went[i][j]){
            ans++;
            walk(i,j);
        }
        printf("%d\n",ans);
    }
}

C++: #include <iostream>
#include <queue>
using namespace std;
struct Point{int x,y;};
int main(){
  int w,h,p[51][51]={},v[51][51]={},i,j,k,o;
  queue <Point> q;
  Point n,b;
  cin >> w >> h;
  while(w!=0){
    for(j=0;j<h;j++){
      for(i=0;i<w;i++){
	cin >> p[i][j];
	v[i][j]=0;
      }
      
    }
    o=0;
    for(j=0;j<h;j++){
      for(i=0;i<w;i++){
	if(v[i][j]==0&&p[i][j]==1){
	  o++;
	  n.x=i;n.y=j;
	  q.push(n);
	  while(!q.empty()){
	    n=q.front();
	    q.pop();
	    v[n.x][n.y]=1;
	    if(n.x+1<w&&v[n.x+1][n.y]==0&&p[n.x+1][n.y]==1) {
	      b.x=n.x+1;b.y=n.y;
	      q.push(b);
	    }
	    if(n.y+1<h&&v[n.x][n.y+1]==0&&p[n.x][n.y+1]==1) {
	      b.x=n.x;b.y=n.y+1;
	      q.push(b);
	    }
	    if(n.x-1>=0&&v[n.x-1][n.y]==0&&p[n.x-1][n.y]==1) {
	      b.x=n.x-1;b.y=n.y;
	      q.push(b);
	    }
	    if(n.y-1>=0&&v[n.x][n.y-1]==0&&p[n.x][n.y-1]==1) {
	      b.x=n.x;b.y=n.y-1;
	      q.push(b);
	    }
	    if(n.x+1<w&&n.y+1<h&&v[n.x+1][n.y+1]==0&&p[n.x+1][n.y+1]==1) {
	      b.x=n.x+1;b.y=n.y+1;
	      q.push(b);
	    }
	    if(n.x-1>=0&&n.y-1>=0&&v[n.x-1][n.y-1]==0&&p[n.x-1][n.y-1]==1) {
	      b.x=n.x-1;b.y=n.y-1;
	      q.push(b);
	    }
	    if(n.x+1<w&&n.y-1>=0&&v[n.x+1][n.y-1]==0&&p[n.x+1][n.y-1]==1) {
	      b.x=n.x+1;b.y=n.y-1;
	      q.push(b);
	    }
	    if(n.x-1>=0&&n.y+1<h&&v[n.x-1][n.y+1]==0&&p[n.x-1][n.y+1]==1) {
	      b.x=n.x-1;b.y=n.y+1;
	      q.push(b);
	    }
	  }
	}
      }
    }
    cout << o << endl;
    cin >> w >> h;
  }
  return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<long long,int> P;


const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int w, h;
int c[55][55];
bool seen[55][55];

void dfs(int x, int y){
    seen[y][x] = true;
    rep(i, 4){
        rep(j, 4){
            int nx = x + dx[i];
            int ny = y + dy[j];
            if (nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
            if (c[ny][nx] == 0 || seen[ny][nx]) continue;
            dfs(nx, ny);
        }
    }
}

int main(){
    vector<int> ans;
    while(true){
        cin >> w >> h;
        if (w == 0 && h == 0) break;
        rep(i, h) rep(j, w) cin >> c[i][j];
        memset(seen, 0, sizeof(seen));
        int cnt = 0;
        rep(y, h){
            rep(x, w){
                if(!seen[y][x] && c[y][x] == 1){
                    cnt ++;
                    dfs(x, y);
                }
            }
        }
        ans.push_back(cnt);
    }
    rep(i, ans.size()) cout << ans[i] << endl;
    return 0;
}