DouKaku?beta

challenge 島の数をカウントする 

m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。

ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。

例：
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ

例：
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ
post comment

Posted feedbacks - Flatten

Nested Hidden

あんまりRubyである必要のないコードですが。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!ruby -Ku

def fill(sima, x, y, color)
  return if x < 0 || y < 0 ||
    !sima[x] || !sima[x][y] ||
    sima[x][y] != color

  sima[x][y] = nil
  fill(sima, x+1, y, color)
  fill(sima, x-1, y, color)
  fill(sima, x, y+1, color)
  fill(sima, x, y-1, color)
end

def next_point(sima)
  sima.size.times{|y|
    sima[0].size.times{|x|
      return [x,y] if sima[x][y]
    }
  }
  nil
end

def sima_scan(str)
  sima = str.split(/\n/).map{|line| line.split(//)}
  result = Hash.new{0}

  while np = next_point(sima)
    x,y = *np
    result[sima[x][y]] += 1
    fill(sima, x, y, sima[x][y])
  end

  result
end

a = "□■■□
□□■□
□■□□
□■■□"

b = "□□□□
■□■□
□■□□
□□□□"

p sima_scan(a)
p sima_scan(b)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# -*- coding: utf-8 -*-

from random import randint

m, n = 4, 3

A = ''.join([''.join([u'□' if randint(0, 1) else u'■' for j in range(n)])+'\n' for i in range(m)])

a = [[0 if A[i*(n+1)+j] == u'□' else 1 for j in range(n)] for i in range(m)]
#for i in a:
#  print i

def f(i, j):
  k = a[i][j]
  a[i][j] = -1
  if i > 0 and a[i-1][j] == k: f(i-1, j)
  if j > 0 and a[i][j-1] == k: f(i, j-1)
  if i < m-1 and a[i+1][j] == k: f(i+1, j)
  if j < n-1 and a[i][j+1] == k: f(i, j+1)

r = [0, 0]
for i in range(m):
  for j in range(n):
    if a[i][j] != -1:
      r[a[i][j]] += 1
      f(i, j)

print A
print 'white: %d\nblack: %d' % tuple(r)

標準入力→標準出力です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#!/bin/bash 
declare -a ISLANDS_WHITE
declare -a ISLANDS_BLACK

function expand_islands() {
    local -i x=$1
    local -i y=$2
    local bw=$3

    local -a islands
    if [ $bw = □ ]; then
        islands=("${ISLANDS_WHITE[@]}")
    else
        islands=("${ISLANDS_BLACK[@]}")
    fi

    local p found
    local -i i n=${#islands[@]}
    for ((i = 0; i < $n; i++)); do
        for p in ${islands[i]}; do
            local -i px=${p%,*} py=${p#*,}
            if (((x == px && y == py + 1) ||
                 (y == py && x == px + 1) )); then
                if [ -z "$found" ]; then
                    islands[i]="${islands[i]} $x,$y"
                    found=$i
                else    # join two islands
                    islands[found]="${islands[found]} ${islands[i]} $x,$y"
                    unset islands[i]
                fi
                break
            fi
        done
    done
    [ -z "$found" ] && islands=("${islands[@]}" "$x,$y")        # new island

    if [ $bw = □ ]; then
        ISLANDS_WHITE=("${islands[@]}")
    else
        ISLANDS_BLACK=("${islands[@]}")
    fi
}

function check_islands() {
    local line
    local -i y=0
    while read -r line; do
        local -i x
        for ((x = 0; x < ${#line}; x++)); do
            expand_islands $x $y ${line:$x:1}
        done
        ((y++))
    done
}

check_islands
echo 白の島は${#ISLANDS_WHITE[@]}
echo 黒の島は${#ISLANDS_BLACK[@]}

ついでに島の大きさも数えてますが、今回は関係ないですね。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.awt.Point;
import java.util.HashMap;
import java.util.Map;


public class Sample219 {
    private static final char NULL = ' ';

    public Map<Character, Integer> scanIslands(String map) {
        String[] lines = map.split("\n");
        char[][] mapdata = new char[lines.length][];
        for (int index = 0; index < lines.length; index++) {
            mapdata[index] = lines[index].toCharArray();
        }

        Map<Character, Integer> result = new HashMap<Character, Integer>();
        for (Point p = getNextPoint(mapdata); p != null; p = getNextPoint(mapdata)) {
            char c = mapdata[p.y][p.x];
            scan(mapdata, p.x, p.y, c);
            Integer count = result.get(c);
            if (count == null) {
                result.put(c, 1);
            } else {
                result.put(c, count + 1);
            }
        }
        return result;
    }

    private Point getNextPoint(char[][] map) {
        for (int y = 0; y < map.length; y++) {
            for (int x = 0; x < map[y].length; x++) {
                if (map[y][x] != NULL) {
                    return new Point(x, y);
                }
            }
        }
        return null;
    }
    private int scan(char[][] map, int x, int y, char c) {
        if (y < 0 || map.length <= y) return 0;
        if (x < 0 || map[y].length <= x) return 0;
        if (map[y][x] != c) return 0;
        int result = 1;
        map[y][x] = NULL;
        result += scan(map, x + 1, y, c);
        result += scan(map, x, y + 1, c);
        result += scan(map, x - 1, y, c);
        result += scan(map, x, y - 1, c);
        return result;
    }

    public static void main(String[] args) {
        Sample219 sample = new Sample219();
        System.out.println(sample.scanIslands(
                "□■■□\n" +
                "□□■□\n" +
                "□■□□\n" +
                "□■■□"));
        System.out.println(sample.scanIslands(
                "□□□□\n" +
                "■□■□\n" +
                "□■□□\n" +
                "□□□□"));
    }
}


ナイーブに。

実行例
*Main> :main
□■■□
□□■□
□■□□
□■■□
白の島: 2個
黒の島: 2個
□□□□
■□■□
□■□□
□□□□
白の島: 1個
黒の島: 3個

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import Control.Arrow
import Data.List
import Data.Function
import qualified System.IO.UTF8 as U

main :: IO ()
main =  mapM_ displayIsland [sample1,sample2]

displayIsland = uncurry (>>) . (printMAP &&& (printAnswer . count . islands))
  where
    printMAP = U.putStr . unlines . map (concatMap show)
    printAnswer (w,b) = mapM_ U.putStrLn ["白の島: "++show w++"個"
                                         ,"黒の島: "++show b++"個"]

data BW = B | W deriving (Eq)

instance Show BW where
  show B = "■"
  show W = "□"

grouping :: [[(Int,BW)]] -> [[(Int,BW)]]
grouping = map (concatMap renumber . adjacent)
  where
    adjacent = groupBy ((==) `on` snd)
    renumber = uncurry replicate . (length &&& minimumBy (compare `on` fst))

count :: [[(Int,BW)]] -> (Int,Int)
count = (cnt *** cnt) . partition ((W ==) . snd) . concat
  where 
    cnt = length . groupBy ((==) `on` fst) . sortBy (compare `on` fst)

islands :: [[BW]] -> [[(Int,BW)]]
islands = fst . head
        . filter (uncurry ((==) . transpose))
        . uncurry zip 
        . (id &&& tail) 
        . iterate (transpose . grouping)
        . numbering 
  where
    numbering = snd . mapAccumL number [0..]  
    number (n:ns) (x:xs) = case number ns xs of (ns',ys) -> (ns',(n,x):ys)
    number ns     []     = (ns,[])

sample1 = [[W,B,B,W]
          ,[W,W,B,W]
          ,[W,B,W,W]
          ,[W,B,B,W]]

sample2 = [[W,W,W,W]
          ,[B,W,B,W]
          ,[W,B,W,W]
          ,[W,W,W,W]]

ロジックが汚いですね。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def text = """\
□□□□
■□■□
□■□□
□□□□"""

def score = ["■":0, "□":0]

board = text.readLines().collect{ it.split("")[1..-1] }
XMAX = board.size() - 1
YMAX = board[0].size() - 1

def eat( mark, x, y ){
    [["x":x-1, "y":y], ["x":x+1, "y":y], ["x":x, "y":y-1], ["x":x, "y":y+1]].findAll{
        (it.x in 0..XMAX) && (it.y in 0..YMAX) && board[it.x][it.y] == mark
    }.each{
        board[it.x][it.y] = "×"
        eat( mark, it.x, it.y )
    }
}

XMAX.times{ x ->
    YMAX.times{ y ->
        def mark = board[x][y]
        if( mark != "×" ){
            score[mark]++
            eat(mark, x, y)
        }
    }
}

println score

しまった・・・誤り発見です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def text = """\
□■■□
■□□□
□□□■
□■■□"""

def score = ["■":0, "□":0]

board = text.readLines().collect{ it.split("")[1..-1] }
XMAX = board.size() - 1
YMAX = board[0].size() - 1

def eatAround( mark, x, y ){
    [["x":x-1, "y":y], ["x":x+1, "y":y], ["x":x, "y":y-1], ["x":x, "y":y+1]].findAll{
        (it.x in 0..XMAX) && (it.y in 0..YMAX) && board[it.x][it.y] == mark
    }.each{
        board[it.x][it.y] = "×"
        eatAround( mark, it.x, it.y )
    }
}

(0..XMAX).each{ x ->
    (0..YMAX).each{ y ->
        def mark = board[x][y]
        if( mark != "×" ){
            score[mark]++
            eatAround(mark, x, y)
        }
    }
}

println score

何度もごめんなさい。 ほんのちょっと修正です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def text = """\
□■■□
■□□■
□□■□
□■■□"""

def score = ["■":0, "□":0]

board = text.readLines().collect{ it.split("")[1..-1] }
XMAX = board.size() - 1
YMAX = board[0].size() - 1

def eat( mark, x, y ){
    board[x][y] = "×"
    // 周辺もいただきます♪
    [["x":x-1, "y":y], ["x":x+1, "y":y], ["x":x, "y":y-1], ["x":x, "y":y+1]].findAll{
        (it.x in 0..XMAX) && (it.y in 0..YMAX) && board[it.x][it.y] == mark
    }.each{
        eat( mark, it.x, it.y )
    }
}

(0..XMAX).each{ x ->
    (0..YMAX).each{ y ->
        def mark = board[x][y]
        if( mark != "×" ){
            score[mark]++
            eat(mark, x, y)
        }
    }
}

println score

これで例の2問は解けました。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//http://ja.doukaku.org/219/
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace どう書く_org島の数をカウントする {
    class Program {
        static void Main(string[] args) {
            string map = @"
□□□□
■□■□
□■□□
□□□□
";
            islandCount(map);

            Console.ReadLine();
        }

        static void islandCount(string map_) {
            List<string> map = new List<string>(map_.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries));
            List<Island> islandList = new List<Island>();
            for(int y = 0; y < map.Count; y++) {
                for(int x = 0; x < map[0].Length; x++) {
                    char cell = map[y][x];
                    bool flag = false;
                    for(int islandIndex = 0; islandIndex < islandList.Count; islandIndex++) {
                        for(int cellIndex = 0; cellIndex < islandList[islandIndex].Count; cellIndex++) {
                            if(isNext(islandList[islandIndex][cellIndex], new Point(x, y)) && map[islandList[islandIndex][0].Y][islandList[islandIndex][0].X] == cell) {
                                islandList[islandIndex].Add(new Point(x, y));
                                flag = true;
                                break;
                            }
                        }
                    }
                    if(!flag) {
                        Island island = new Island();
                        island.Add(new Point(x, y));
                        islandList.Add(island);
                    }
                }
            }

            while(islandListMarge(islandList, map)) { }

            Console.WriteLine("白の島は" + islandList.Count<Island>((x) => (map[x[0].Y][x[0].X] == '□')).ToString() + "つ");
            Console.WriteLine("黒の島は" + islandList.Count<Island>((x) => (map[x[0].Y][x[0].X] == '■')).ToString() + "つ");
        }

        static bool islandListMarge(List<Island> islandList, List<string> map) {
            for(int i = 0; i < islandList.Count; i++) {
                for(int j = 0; j < islandList.Count; j++) {
                    if(i == j) continue;
                    Island a = islandList[i];
                    Island b = islandList[j];
                    if(map[a[0].Y][a[0].X] != map[b[0].Y][b[0].X]) continue;
                    for(int a_ = 0; a_ < a.Count; a_++) {
                        for(int b_ = 0;b_ < b.Count; b_++) {
                            if(isNext(a[a_], b[b_])) {
                                a.AddRange(b);
                                islandList.Remove(b);
                                return true;
                            }
                        }
                    }
                }
            }
            return false;
        }

        static bool isNext(Point a, Point b) {
            Point tmpB = b;
            bool r = false;
            for(int i = -1; i <= 1; i++) {
                for(int j = -1; j <= 1; j++) {
                    if(i * j != 0) continue;
                    tmpB.Offset(i, j);
                    if(a == tmpB) r = true;
                    tmpB = b;
                }
            }
            return r;
        }
    }

    class Island :List<Point> {

    }
}

画像に変換して、塗っていってます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
map="□■■□
□□■□
□■□□
□■■□"
tmpとは配列
mapを改行で区切るを反復
    tmpの回数-1に(対象を文字列分解の表行列交換)を配列一括挿入
map_h=aで改行の出現回数+1
map_w=aから改行まで切り取るの文字数
island_black=0
island_white=0
島とはイメージ
島の高さはmap_h
島の幅はmap_w
Iで0からmap_h-1まで繰り返す
    Jで0からmap_w-1まで繰り返す
        もし、tmp[I,J]="■"ならば
            島のJ,Iへ黒色を点描画
Iで0からmap_h-1まで繰り返す
    Jで0からmap_w-1まで繰り返す
        島のJ,Iを点取得で条件分岐
            黒色ならば
                island_black=island_black+1
                島のJ,Iを緑色で塗る
            白色ならば
                island_white=island_white+1
                島のJ,Iを緑色で塗る
「黒い島は{island_black}個
白い島は{island_white}個」を言う


実質C言語ですね。
C++らしいのも考えたい…。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>

static const int Width  = 4;
static const int Height = 4;

void markCell(int row, int col, const char cells[Height][Width], bool marks[Height][Width])
{
    marks[row][col] = true;
    if((row > 0         ) && ( ! marks[row - 1][col]) && (cells[row][col] == cells[row - 1][col])) markCell(row - 1, col, cells, marks);
    if((row < Height - 1) && ( ! marks[row + 1][col]) && (cells[row][col] == cells[row + 1][col])) markCell(row + 1, col, cells, marks);
    if((col > 0)          && ( ! marks[row][col - 1]) && (cells[row][col] == cells[row][col - 1])) markCell(row, col - 1, cells, marks);
    if((col < Width - 1)  && ( ! marks[row][col + 1]) && (cells[row][col] == cells[row][col + 1])) markCell(row, col + 1, cells, marks);
}

void doukaku219(const char cells[Height][Width])
{
    int  countWhite = 0;
    int  countBlack = 0;
    bool marks[Height][Width];

    for(int row = 0; row < Height; ++row)
    {
        for(int col = 0; col < Width; ++col)
        {
            marks[row][col] = 0;
        }
    }

    for(int row = 0; row < Height; ++row)
    {
        for(int col = 0; col < Width; ++col)
        {
            if( ! marks[row][col])
            {
                if(cells[row][col] == 0)
                {
                    ++countWhite;
                }
                else
                {
                    ++countBlack;
                }
                marks[row][col] = true;
            }
            markCell(row, col, cells, marks);
        }
    }

    std::cout << "白の島は" << countWhite << "つ" << std::endl;
    std::cout << "黒の島は" << countBlack << "つ" << std::endl;
}

int main(int, char* [])
{
    const char probrem0[Width][Height] =
    {
        { 0, 1, 1, 0 },
        { 0, 0, 1, 0 },
        { 0, 1, 0, 0 },
        { 0, 1, 1, 0 }
    };

    const char probrem1[Width][Height] =
    {
        { 0, 0, 0, 0 },
        { 1, 0, 1, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 } 
    };

    doukaku219(probrem0);
    doukaku219(probrem1);

    return 0;
}

ログインし忘れた orz。


おまけにこまかいミスがちらほら。とほほ orz。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>

static const int Width  = 4;
static const int Height = 4;

void markCell(int row, int col, const char cells[Height][Width], bool marks[Height][Width])
{
    marks[row][col] = true;
    if((row > 0         ) && ( ! marks[row - 1][col]) && (cells[row][col] == cells[row - 1][col])) markCell(row - 1, col, cells, marks);
    if((row < Height - 1) && ( ! marks[row + 1][col]) && (cells[row][col] == cells[row + 1][col])) markCell(row + 1, col, cells, marks);
    if((col > 0)          && ( ! marks[row][col - 1]) && (cells[row][col] == cells[row][col - 1])) markCell(row, col - 1, cells, marks);
    if((col < Width - 1)  && ( ! marks[row][col + 1]) && (cells[row][col] == cells[row][col + 1])) markCell(row, col + 1, cells, marks);
}

void doukaku219(const char cells[Height][Width])
{
    int  countWhite = 0;
    int  countBlack = 0;
    bool marks[Height][Width];

    for(int row = 0; row < Height; ++row)
    {
        for(int col = 0; col < Width; ++col)
        {
            marks[row][col] = 0;
        }
    }

    for(int row = 0; row < Height; ++row)
    {
        for(int col = 0; col < Width; ++col)
        {
            if( ! marks[row][col])
            {
                if(cells[row][col] == 0)
                {
                    ++countWhite;
                }
                else
                {
                    ++countBlack;
                }
                markCell(row, col, cells, marks);
            }
        }
    }

    std::cout << "白の島は" << countWhite << "つ" << std::endl;
    std::cout << "黒の島は" << countBlack << "つ" << std::endl;
}

int main(int, char* [])
{
    const char problem0[Width][Height] =
    {
        { 0, 1, 1, 0 },
        { 0, 0, 1, 0 },
        { 0, 1, 0, 0 },
        { 0, 1, 1, 0 }
    };

    const char problem1[Width][Height] =
    {
        { 0, 0, 0, 0 },
        { 1, 0, 1, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 } 
    };

    doukaku219(problem0);
    doukaku219(problem1);

    return 0;
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>

static
void walk(char *board, int W, int H, int pos, int color)
{
    if (board[pos] == color) {
        int row = pos / W, col = pos % W;
        board[pos] = -1;
        if (col > 0) walk(board, W, H, pos - 1, color);
        if (row > 0) walk(board, W, H, pos - W, color);
        if (col < W - 1) walk(board, W, H, pos + 1, color);
        if (row < H - 1) walk(board, W, H, pos + W, color);
    }
}
static
void solve(char *board, int width, int height, int *result)
{
    int pos, size = width * height;
    for (pos = 0; pos < size; ++pos)
        if (board[pos] >= 0) {
            ++result[board[pos]];
            walk(board, width, height, pos, board[pos]);
        }
}
static
void pr(const char **colors, const int *result)
{
    int i;
    for (i = 0; colors[i]; ++i)
        printf("%sの島は%dつ\n", colors[i], result[i]);
}
int main(void)
{
    const char *colors[] = { "白", "黒", 0 };
    char a1[] = { 0,1,1,0, 0,0,1,0, 0,1,0,0, 0,1,1,0 };
    char a2[] = { 0,0,0,0, 1,0,1,0, 0,1,0,0, 0,0,0,0 };
    int r1[] = { 0, 0 }, r2[] = { 0, 0 };
    solve(a1, 4, 4, r1), pr(colors, r1);
    solve(a2, 4, 4, r2), pr(colors, r2);
    return 0;
}

特にひねりもなく。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
(use srfi-43)

(define (count-island target board)
  (let ((h (vector-length board))
        (w (vector-length (vector-ref board 0)))
        (v (vector-map (lambda (i x) (vector-copy x)) board))
        (c (gensym)))
    (define (bref b x y) (vector-ref (vector-ref b y) x))
    (define (bset! b x y o) (vector-set! (vector-ref b y) x o))
    (define (fill-paint! x y)
      (let loop ((x x) (y y))
        (cond ((or (negative? x) (>= y h)))
              ((>= x w)
               (loop 0 (+ y 1)))
              ((equal? (bref v x y) target)
               (bset! v x y c)
               (loop (- x 1) y)
               (loop (+ x 1) y)
               (loop x (+ y 1))))))
    (let loop ((x 0) (y 0) (n 0))
      (cond ((>= y h)
             n)
            ((>= x w)
             (loop 0 (+ y 1) n))
            ((equal? (bref v x y) target)
             (fill-paint! x y)
             (loop (+ x 1) y (+ n 1)))
            (else
             (loop (+ x 1) y n))))))

(let ((bs '(#(#(0 1 1 0)
              #(0 0 1 0)
              #(0 1 0 0)
              #(0 1 1 0))
            #(#(0 0 0 0)
              #(1 0 1 0)
              #(0 1 0 0)
              #(0 0 0 0)))))
  (for-each (lambda (b)
              (format #t "白の島は‾Aつ‾%黒の島は‾Aつ‾%"
                      (count-island 0 b)
                      (count-island 1 b)))
            bs))


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
WHITE = "□"
BLACK = "■"

AREA = [
  %w[□ □ □ □],
  %w[■ □ ■ □],
  %w[□ ■ □ □],
  %w[□ □ □ □]
]

Mark = Array.new(AREA.size).map{ Array.new(AREA[0].size, false) }

def marking(x, y, color)
  return false if x < 0 || x >= AREA.size || y < 0 || y >= AREA[0].size || AREA[x][y] != color || Mark[x][y] != false

  Mark[x][y] = true

  marking(x,   y+1, color)
  marking(x+1, y,   color)
  marking(x,   y-1, color)
  marking(x-1, y,   color)

  true
end

def loop(counter, color)
  (0...AREA.size).each do |x|
    (0...AREA[x].size).each do |y|
      counter += 1 if marking(x, y, color)
    end
  end

  counter
end

puts "白の島は#{loop(0, WHITE)}です。"
puts "黒の島は#{loop(0, BLACK)}です。"

Scalaの練習として。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
object Tile extends Enumeration {
  val White, Black, Fill = Value
}
import Tile._
  
class Q8053 {
  def countIsland(str : String, target : Value) = {
    var data = parse(str)
    var result = 0
    for (y <- 0 to data.length - 1; x <- 0 to data(y).length - 1) {
      if (data(y)(x) == target) {
        fill(data, y, x, target)
        result += 1
      }
    }
    result
  }

  def parse(str : String) = {
    str.lines.toList.map(_.toList.map( x => if (x == '□') White else Black).toArray).toArray
  }

  def fill(data : Array[Array[Value]], y :Int, x :Int, target : Value):Unit = {
    if (y < 0 || y >= data.length || x < 0 || x >= data(y).length || data(y)(x) != target) {
      return
    }
    data(y)(x) = Fill
    fill(data, y-1, x, target)
    fill(data, y+1, x, target)
    fill(data, y, x-1, target)
    fill(data, y, x+1, target)
  }
}

object Main {
  val sample1 = """□■■□
                  |□□■□
                  |□■□□
                  |□■■□""".stripMargin

  val sample2 = """□□□□
                  |■□■□
                  |□■□□
                  |□□□□""".stripMargin

  def main(args : Array[String]) = {
    var q = new Q8053
    println(q countIsland(sample1, White)) // 2
    println(q countIsland(sample1, Black)) // 2
    println(q countIsland(sample2, White)) // 1
    println(q countIsland(sample2, Black)) // 3
  }

Squeak Smalltalk で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
| map islands deltas |
map := Matrix rows: 4 columns: 4 contents: 
    '□□□□',
    '■□■□',
    '□■□□',
    '□□□□'.
deltas := {0@0. -1@0. 0@-1. 0@1. 1@0}.
islands := OrderedCollection new.
map withIndicesDo: [:elem :row :col |
    | neighs |
    neighs := (deltas select: [:dt |
        (map at: row + dt y at: col + dt x ifInvalid: nil) = elem]) asSet + (col@row).
    islands copy do: [:is |
        (is intersection: neighs) ifNotEmpty: [neighs addAll: (islands remove: is)]].
    islands add: neighs].
^(islands collect: [:is |
    | pos |
    pos := is anyOne.
    map at: pos y at: pos x]) asBag sortedCounts asArray
"=> {3->$■ . 1->$□} "

匿名で投稿してしまったのと気に食わない部分があったので少し修正して。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
object Q8053 {
  object Tile extends Enumeration {
    val White, Black, Fill = Value
  }
  import Tile._
  
  def countIsland(str : String, target : Value) = {
    var data = parse(str)
    var result = 0
    for (y <- 0 to data.length - 1; x <- 0 to data(y).length - 1) {
      if (data(y)(x) == target) {
        fill(data, y, x, target)
        result += 1
      }
    }
    result
  }

  def parse(str : String) = {
    str.lines.toList.map(_.toList.map( x => if (x == '□') White else Black).toArray).toArray
  }

  def fill(data : Array[Array[Value]], y :Int, x :Int, target : Value):Unit = {
    if (y < 0 || y >= data.length || x < 0 || x >= data(y).length || data(y)(x) != target) {
      return
    }
    data(y)(x) = Fill
    fill(data, y-1, x, target)
    fill(data, y+1, x, target)
    fill(data, y, x-1, target)
    fill(data, y, x+1, target)
  }
}

普通なやり方で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
(defun fill-map (a c i j)
  (destructuring-bind (h w) (array-dimensions a)
    (and (< -1 i h)
         (< -1 j w)
         (eql (aref a i j) c)
         (let ((c1 (aref a i j)))
           (setf (aref a i j) nil)
           (fill-map a c1 (1- i) j)
           (fill-map a c1 (1+ i) j)
           (fill-map a c1 i (1- j))
           (fill-map a c1 i (1+ j))))))

(defun count-islands (m)
  (let ((a (list (cons :W 0) (cons :B 0))))
    (dotimes (i (array-dimension m 0))
      (dotimes (j (array-dimension m 1))
        (when (aref m i j)
          (incf (cdr (assoc (aref m i j) a)))
          (fill-map m (aref m i j) i j))))
    a))

;;; tests
(defun print-map (m)
  (dotimes (i (array-dimension m 0))
    (dotimes (j (array-dimension m 1) (terpri))
      (princ (ecase (aref m i j)
               (:B (or (name-char "BLACK_SQUARE") #\B))
               (:W (or (name-char "WHITE_SQUARE") #\W)))))))

(defun test (m)
  (format t "Map:~%")
  (print-map m)
  (let ((a (count-islands m)))
    (format t "white: ~D~%black:~D~%"
            (cdr (assoc :W a)) (cdr (assoc :B a)))))

(test #2A((:W :B :B :W)
          (:W :W :B :W)
          (:W :B :W :W)
          (:W :B :B :W)))
(test #2A((:W :W :W :W)
          (:B :W :B :W)
          (:W :B :W :W)
          (:W :W :W :W)))


・１行ずつ処理。
・列をビットに対応させて連結情報は整数のリストで保持。
  （例えば [W,B,W,W] という行は [[1,12],[2]] に変換）
・縦に連結しているかはビット論理積が非０かで判定。
・連結は加算。（例えば [W,B,W,W] で左の１個の W と右の２個の W が
  連結していることがわかった場合は 1+12（つまり 13）で表せる）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import Data.List
import Data.Bits

data BW = B | W deriving (Eq)

conv :: [BW] -> [[Int]]
conv xs = map (map (sum.map snd).filter (not.null))
  $ transpose $ unfoldr f $ zip xs $ iterate (2*) 1  where
  f [] = Nothing 
  f zs = Just([ws,bs],zs'') where
    (ws,zs' ) = span ((==W).fst) zs
    (bs,zs'') = span ((==B).fst) zs'

count :: [[BW]] -> [Int]
count rows = map (sum.concat) $ transpose $ snd
  $ mapAccumL g [[],[]] $ (++ [[[],[]]]) $ map conv rows  where
  g yss xss = unzip $ zipWith (mapAccumL h) xss yss
  h xs y = if null cs then (ds, 1) else (sum cs: ds, 0)  where
    (cs,ds) = partition ((/=0).(y.&.)) xs

{-
> count [[W,W,W,W],[B,W,B,W],[W,B,W,W],[W,W,W,W]]
[1,3]
-}


#8081 を ruby で。
each を使うか inject を使うか迷う。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def conv(xs)
  d, wbs = 1, [[],[]]
  xs.scan(/(W*)(B*)/){|wb|
    [0,1].each{|i|
      m = 1<<wb[i].length
      wbs[i] << (m-1)*d if (m > 1)
      d *= m
    }
  }
  {:w => wbs[0], :b => wbs[1]}
end

def count(rows)
  zs2 = (rows.map{|xs|conv xs}+[{:w=>[],:b=>[]}]).inject(:w=>[[],0],:b=>[[],0]){|zs,xs|
    {:w => g(xs[:w],*zs[:w]), :b => g(xs[:b],*zs[:b])}
  }
  {:w => zs2[:w][1], :b => zs2[:b][1]}
end

def g(xs,ys,m)
  ys2 = ys.inject(xs){|as,y|
      bs, c = [], 0
      as.each{|z| if (z&y != 0) then c += z; else bs << z; end}
      if (c > 0) then bs << c; else m += 1; bs; end
  }
  [ys2,m]
end

p(count(["WBBW","WWBW","WBWW","WBBW"])) # => {:b=>2, :w=>2}
p(count(["WWWW","BWBW","WBWW","WWWW"])) # => {:b=>3, :w=>1}


Perl がないようなので１つ。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
use strict;
my $m = int(rand 3) + 4; my $n = $m + int(rand(7 - $m));
my (%board, %group);

foreach my $i (1 .. $m) {
  foreach my $j (1 .. $n) {
    my $key = $i . $j;
    $board{$key} = int(rand 2);
    print $board{$key} ? '■' : '□';
    print "\n" if $j == $n;
    my $flag = 0;
    if ($i > 1) {
      my $up_key = $key - 10;
      if ($board{$key} == $board{$up_key}) {
        foreach my $item (@{$group{$board{$key}}}) {
          if ($item =~ /$up_key/) { $item .= ":$key"; $flag = 1; }
        }
      }
    }
    if ($j > 1) {
      my $left_key = $key - 1;
      if ($board{$key} == $board{$left_key}) {
        $flag++;
        if ($flag == 1) {
          foreach my $item (@{$group{$board{$key}}}) {
            $item .= ":$key" if $item =~ /$left_key/;
          }
        } else {
          my ($same) = grep { $group{$board{$key}}->[$_] =~ /$key/ } 0 .. $#{$group{$board{$key}}};
          my ($left) = grep { $group{$board{$key}}->[$_] =~ /$left_key/ } 0 .. $#{$group{$board{$key}}};
          if ($same != $left) {
            $group{$board{$key}}->[$same] = join ':', sort
              split /:/, "$group{$board{$key}}->[$same]:$group{$board{$key}}->[$left]";
            splice(@{$group{$board{$key}}}, $left, 1);
          }
        }
      }
    }
    push @{$group{$board{$key}}}, $key unless $flag;
  }
}

print "\n□の島: ", scalar(@{$group{0}}), "\n  ", join(', ', @{$group{0}}), "\n";
print "\n■の島: ", scalar(@{$group{1}}), "\n  ", join(', ', @{$group{1}}), "\n";

BASICのpaint文の処理に近いのかな。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def paint(s, x, y, value) {
    if (x < 0 || y < 0 || x >= s[0].size() || y >= s.size() || s[y][x]==value) {
        return
    }
    s[y][x] = value
    paint(s, x+1, y, value)
    paint(s, x-1, y, value)
    paint(s, x, y+1, value)
    paint(s, x, y-1, value)
}
def count(data) {
    [0,1].each { color ->
        s = data.collect{it.collect{it=="■"?0:1}};
        count = 0
        (0..<s.size()).each {y->
            (0..<s[y].size()).each { x->
                if (s[y][x] != color) {
                    paint(s, x, y, color)
                    count++
                }
            }
        }
        println count
    }
}

count(["□■■□",
       "□□■□",
       "□■□□",
       "□■■□"])

count(["□□□□",
       "■□■□",
       "□■□□",
       "□□□□"])


PHPで書く人がいなかったので。
１．基本的に左上から右下へ捜査していく

２．特定の位置から、右、下の位置を基本的につながっているか確認する。
つながっている場合は、同じ島の番号を振る

３．途中でぐるっと回ってつながっていることがわかったらその時点で、
島の番号を振りなおして、島の数を修正する。

上下左右の４点を調べていく方法は
なんとなくありきたりなのでやめました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
$w = $h = 4;

$a = array(
      array(
        array(0,1,1,0)
       ,array(0,1,0,0)
       ,array(0,0,1,0)
       ,array(0,1,1,0)
      ),
      array(
        array(0,0,0,0)
       ,array(1,0,1,0)
       ,array(0,1,0,0)
       ,array(0,0,0,0)
      )
    );


function revSima($a0){
  global $w,$h;
    $a1 = array();
    for($i=0;$i<$w;$i++){
      for($j=0;$j<$h;$j++){
        $a1[$i][$j] = $a0[$i][$j] === 0 ? 1 : 0;
      }
    }
    return $a1;
}

function countSima($a0){
  global $w,$h;
  
  $k = array();
    $g = 1;
    
    for($i=0;$i<$w;$i++){

      for($j=0;$j<$h;$j++){
    
        if($a0[$i][$j] === 0) continue;

            if($a0[$i][$j] === 1){
              $a0[$i][$j] = ++$g;
              $k[$g] = 1;
            }
          $c = $a0[$i][$j];

          if($i + 1 < $h && $a0[$i + 1][$j] === 1){
            $a0[$i + 1][$j] = $c;
          }
          
          if($j + 1 < $w && $a0[$i][$j + 1] === 1){
            $a0[$i][$j + 1] = $c;
            
          }elseif($j + 1 < 4 && $a0[$i][$j + 1] > 1 ){

            for($m=0;$m<$i+1;$m++){
              for($n=0;$n<4;$n++){
                if($a0[$m][$n] === $c){
                  $a0[$m][$n] = $a0[$i][$j + 1];
                    }
              }
            }
            unset($k[$c]);
          }
      }
    }
    return count(array_keys($k));
}

foreach($a as $v){
  echo '(Black,White) = ('. countSima($v) . ','. countSima(revSima($v)) . ')' . "\n";
}

島の数を答えればいいので、 つながっていれば島の数を数えなおす ループを改定しました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
$w = $h = 4;

$a = array(
      array(
        array(0,1,1,0)
       ,array(0,1,0,0)
       ,array(0,0,1,0)
       ,array(0,1,1,0)
      ),
      array(
        array(0,0,0,0)
       ,array(1,0,1,0)
       ,array(0,1,0,0)
       ,array(0,0,0,0)
      )
    );


function revSima($a0){
  global $w,$h;
    $a1 = array();
    for($i=0;$i<$w;$i++){
      for($j=0;$j<$h;$j++){
        $a1[$i][$j] = $a0[$i][$j] === 0 ? 1 : 0;
      }
    }
    return $a1;
}

function countSima($a0){
  global $w,$h;
  
  $k = array();
    $g = $c = 1;
    for($i=0;$i<$w;$i++){

      for($j=0;$j<$h;$j++){
    
        if($a0[$i][$j] === 0) continue;

            if($a0[$i][$j] === 1){
              $a0[$i][$j] = ++$g;
              $k[$g] = 1;
            }
          $c = $a0[$i][$j];

          if($i + 1 < $h && $a0[$i + 1][$j] === 1){
            $a0[$i + 1][$j] = $c;
          }
          
          if($j + 1 < $w && $a0[$i][$j + 1] === 1){
            $a0[$i][$j + 1] = $c;
            
          }elseif($j + 1 < $w && $a0[$i][$j + 1] > 1 && $c > $a0[$i][$j + 1] ){

            for($m=$i; $m<=$i+1; $m++){
              for($n=0; $n<=$j; $n++){
                if($a0[$m][$n] === $c){
                  $a0[$m][$n] = $a0[$i][$j + 1];
                }
              }
            }
            unset($k[$c]);
          }
      }
    }
    return count(array_keys($k));
}

foreach($a as $v){
  echo '(Black,White) = ('. countSima($v) . ','. countSima(revSima($v)) . ')' . "\n";
}


初投稿です。
変態的な実装ができないかと考えていたのですが、
最適化していくうちに#8104さんと似た考え方になってしまいました。
秀丸の新規窓の左上に島を書いて、マクロ実行です。

考え方は以下の通りです。
１．左上から右下に向かって横にスキャン
２．上と左の島連番取得
３．取得出来なければ新しい島＆島数プラス
４．上と左の島連番が一致しない場合、左の島連番を塗り直し＆島数マイナス

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#xcharlen=2;
$wchar="□";
$bchar="■";

#xlen=4;
#ylen=4;

#wcnt=0;
#bcnt=0;
##x=0;
##y=0;
##serial=1;

    while( ##y < #ylen ) {
        ##x=0;
        while( ##x < #xlen ) {
            call GETCHAR ##x, ##y;
            $$c = $$return;
            if( ##y == 0 ) {
                ##no = ##serial;
            } else {
                call GETCHAR ##x, ##y-1;
                if( $$return == $$c ) {
                    ##no = #mtx[##y-1][##x];
                } else {
                    ##no = ##serial;
                }
            }
            if( ##x > 0 ) {
                call GETCHAR ##x-1, ##y;
                if( $$return == $$c ) {
                    if( ##no == ##serial ) {
                        ##no = #mtx[##y][##x-1];
                    } else if( ##no != #mtx[##y][##x-1] ) {
                        call RENUM ##no, #mtx[##y][##x-1], ##y, $$c;
                    }
                }
            }
            #mtx[##y][##x] = ##no;
            if( ##no == ##serial ) {
                call CNTISLAND $$c, 1;
                ##serial = ##serial+1;
            }
            ##x = ##x+1;
        }
        ##y = ##y+1;
    }

    message "白の島は" + str(#wcnt) + "つ\n" + "黒の島は" + str(#bcnt) + "つ";

    endmacro;

RENUM:
    ##i=0;
    while( ##i < ##3+1 ) {
        ##j=0;
        while( ##j < #xlen ) {
            if( #mtx[##i][##j]==##2 ) {
                #mtx[##i][##j]=##1;
            }
            ##j=##j+1;
        }
        ##i=##i+1;
    }

    call CNTISLAND $$4, -1;

    return;

CNTISLAND:
    if( $$1 == $wchar ) {
        #wcnt=#wcnt+##2;
    } else {
        #bcnt=#bcnt+##2;
    }

    return;

GETCHAR:
    ##x1 = ##1 * #xcharlen;
    ##x2 = ##x1 + #xcharlen;
    $$res=gettext(##x1, ##2, ##x2, ##2, 0);

    return $$res;

調べる位置が、右と下　左と上の違い なのでそんな大差はないのかもしれないけど、 スキャンする方向が、左上から右下ということを 考えると、#8104 より、こっちのほうが、島の塗り直しがシンプルでいいですね。


かなりムダなことをしている…
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <stdexcept>

template <class cell> class Field {
public:
    Field(int width, int height) : width_(width), height_(height), v_(width * height) {}
    void initialize(std::string data){
        std::copy(data.begin(), data.end(), v_.begin());
    }

    void print(){
        int i=0;
        for(std::vector<cell>::const_iterator ite=v_.begin();ite!=v_.end();++ite){
            std::cout << *ite;
            ++i;
            if(0==i%width_){
                i=0;
                std::cout << '\n';
            }
        }
        std::cout << std::endl;
    }
    
    cell& get(int x, int y) throw(std::out_of_range){
        if(x < 0 || x >= width_)
            throw std::out_of_range("out of range by x");
        if(y < 0 || y >= height_)
            throw std::out_of_range("out of range by y");
        return v_.at(x + y * width_);
    }

    int get_width() { return width_; }
    int get_height() { return height_; }

private:
    int width_;
    int height_;
    std::vector<cell> v_;
};

typedef int color;

class Cell {
public:
    Cell() : kind_(none), c_code_(0) {}
    Cell(const char& kind) : c_code_(0) {
        switch(kind){
        case 'W':
            kind_ = white;
            break;
        case 'B':
            kind_ = black;
            break;
        default:
            kind_= none;
        }
    }
    Cell(const Cell& c) : kind_(c.kind_), c_code_(c.c_code_) {}
    
    const color& get_color() const { return c_code_;}

    const char toString() const{
        if(kind_==white)
            return 'W';
        else if(kind_==black)
            return 'B';
        return ' ';
    }

    friend void paint(Field<Cell>& f, int x, int y, Cell *neighbor = NULL);

private:
    enum Kind { none, white, black };
    
    Kind kind_;
    mutable color c_code_;
};

std::ostream& operator << ( std::ostream& os , const Cell& c ){
    os << c.toString() ;
    return  os ;
}

static color black = 0, white = 0;

void paint(Field<Cell>& f, int x, int y, Cell *neighbor){
    //範囲外指定の場合は、処理しない
    if(x < 0 || x >= f.get_width()) return ;
    if(y < 0 || y >= f.get_height()) return ;

    Cell& c = f.get(x, y);
    if(c.c_code_ != 0) return ; //既に塗られている場合は、必要ない
    if(neighbor != NULL){ //隣のセルから呼び出された
        if(neighbor->kind_ != c.kind_) return ; //隣のセルと同種のセルでない場合は、処理しない

        c.c_code_ = neighbor->c_code_;//同じ色にする
    } else {
        color  set_color;
        switch(c.kind_){
        case Cell::Kind::black:
            set_color = --black;
            break;
        case Cell::Kind::white:
            set_color = ++white;
            break;
        default:
        // 未初期化、あり得ない
            throw "find unsetting kind of cell!";
        }
        c.c_code_ = set_color;
    }
    //周りのセルを塗る
    paint(f, x - 1, y, &c);
    paint(f, x + 1, y, &c);
    paint(f, x, y - 1, &c);
    paint(f, x, y + 1, &c);
}

void painter(Field<Cell>& f){
    int width =f.get_width();
    int height=f.get_height();

    for(int x=0;x < width ; ++x)
        for(int y=0; y < height ; ++y)
            paint(f, x, y);
}

int main(){
    std::string data1(
        "WBBW"
        "WWBW"
        "WBWW"
        "WBBW"
    );
    std::string data2(
        "WWWW"
        "BWBW"
        "WBWW"
        "WWWW"
    );

    Field<Cell> f1(4, 4);
    f1.initialize(data1);
    f1.print();
    painter(f1); //f1 を塗り分ける
    //塗り分けるのに要した色数
    std::cout << "black:" << -black << '\n';
    std::cout << "white:" << white << '\n';
    std::cout << std::endl;

    black=white=0;
    Field<Cell> f2(4, 4);
    f2.initialize(data2);
    f2.print();
    painter(f2);
    std::cout << "black:" << -black << '\n';
    std::cout << "white:" << white << '\n';
    std::cout << std::endl;
}

仕様記述言語Alloyでやってみました。

島の判別のロジックより、マップを書くほう（23行目以降）が長くなってしまいました。

最後のnoExampleはマップも自動生成しながら解きます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
one sig Answer {
  width, height, blackIslands, whiteIslands: Int
}
{
  blackIslands = #{x: Island | some g:Square | g.island = x and g.color = Black} 
  whiteIslands = #{x: Island | some g:Square | g.island = x and g.color = White} 
}
sig Square {
  row, col: Int,
  left, down: lone Square,
  color: Color,
  island: Island
}
abstract sig Color {}
one sig White, Black extends Color {}
sig Island {}
fact islandLaw {
  all disj s,s': Square | s.island = s'.island iff
      s' in s.^{s1,s2: Square |
        (s2 in s1.(left+down) or s1 in s2.(left+down)) and s1.color = s2.color } 
}

fact squareLaws {
  all s1, s2: Square | s1.row = s2.row and s1.col = s2.col iff s1 = s2
  all g: Square {
    g.col = Answer.width - 1 => no g.left
      else g.left.row = g.row and g.left.col = g.col + 1
    g.row = Answer.height - 1 => no g.down
      else g.down.row = g.row + 1 and g.down.col = g.col
  }
}
pred setSquare (r,c: Int, cl: Color) {
  some g: Square | g.row = r and g.col = c and g.color = cl
}

pred example1 () {
  Answer.width = 4 and Answer.height = 4
  setSquare[0,0,White] and setSquare[0,1,Black]
    and setSquare[0,2,Black] and setSquare[0,3,White]
  setSquare[1,0,White] and setSquare[1,1,White]
    and setSquare[1,2,Black] and setSquare[1,3,White]
  setSquare[2,0,White] and setSquare[2,1,Black]
    and setSquare[2,2,White] and setSquare[2,3,White]
  setSquare[3,0,White] and setSquare[3,1,Black]
    and  setSquare[3,2,Black] and setSquare[3,3,White]
}
run example1 for 16

pred example2 () {
  Answer.width = 4 and Answer.height = 4
  setSquare[0,0,White] and setSquare[0,1,White]
    and setSquare[0,2,White] and setSquare[0,3,White]
  setSquare[1,0,Black] and setSquare[1,1,White]
    and setSquare[1,2,Black] and setSquare[1,3,White]
  setSquare[2,0,White] and setSquare[2,1,Black]
    and setSquare[2,2,White] and setSquare[2,3,White]
  setSquare[3,0,White] and setSquare[3,1,White]
    and setSquare[3,2,White] and setSquare[3,3,White]
}
run example2 for 16

pred noExample () {
  Answer.width = 4 and Answer.height = 4
}
run example2 for 16

折角なので1行にしてみました. 内容は以下の通りです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ruby -e "puts proc{|w,b,c| w.each_with_index{|line,i| line.each_with_index{|x,j| b[(pos=[i,j]).first][pos.last] = (b.to_enum.map.with_index{|line,i| line.to_enum.map.with_index{|x,j| [x,[i,j]]}}.inject([]){|a,b| a + b}.detect(nil){|y,cpos| y && y.match(/\A\d#{w[cpos.first][cpos.last]}/) && proc{|w,pos,cpos,result| con_aux = proc{|b,pos,cpos,e,dir,his| result or pos == cpos && result = true or dir.map{|d| d.zip(cpos).map{|a,b| a+b}}.select{|c| c.all?{|c| (0...4).include?(c)}}.each{|c| con_aux.(b,pos,c,e,dir,his+[c]) if e == b[c.first][c.last] and !his.include?(c)}} and w[pos.first][pos.last] == w[cpos.first][cpos.last] and con_aux.(w,pos,cpos,w[cpos.first][cpos.last],[*-1..1].product([*-1..1]).select{|a,b| (a+b).abs == 1},[cpos]) and result}.(w,pos,cpos,nil)} or [(c[x]+=1).to_s+x.to_s]).first}} and c}.(w=Array.new(n=4){Array.new(n){[:b,:w].choice}},Array.new(n){Array.new(n){nil}},{:b => 0, :w => 0}), w.map(&:join)"
class World
  include Enumerable
  def initialize(n=4,&proc) @a = Array.new(n){Array.new(n,&proc)}  end
  def each()
    @a.each_with_index{|line,i| line.each_with_index{|e,j| yield [e,[i,j]]}} end
  def []=(pos,val) @a[pos.first][pos.last] = val end
  def [](pos)      @a[pos.first][pos.last] end
  def inspect()    @a.map(&:join).join("\n")+"\n"  end
end
class Main
  def initialize
    @w, @c = World.new{rand(2).zero? ? :b : :w}, {:b => 0, :w => 0}
    p @w, scan(World.new{nil}), @c
  end
  def scan(b)
    @w.each{|x,pos| b[pos] = (b.detect(nil){|y,cpos| y && y.match(/\A\d#{@w[cpos]}/) && connect?(pos,cpos)} or ["#{@c[x]+=1}#{x}"]).first} and b
  end
  def connect?(pos,cpos,result=nil)
    con_aux = proc{|b,pos,cpos,e,dir,his| result or pos == cpos && result = true or dir.map{|c| c.zip(cpos).map{|a,b| a+b}}.select{|c| c.all?{|c| (0...4).include?(c)}}.each{|c| con_aux.(b,pos,c,e,dir,his+[c]) if e == b[c] and !his.include?(c)}}
    @w[pos] == @w[cpos] and con_aux.(@w,pos,cpos,@w[cpos],[*-1..1].product([*-1..1]).select{|a,b| (a+b).abs == 1},[cpos]) and result
  end
end

クラスを作ってやってみましたが、コードが増えてしまい、あんまりいいこと無しです。

まぁしかし、Groovyの勉強にはなったかな。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
def board1 = new Board('''\
□□□□
■□■□
□■□□
□□□□'''
)
board1.out()
board1.search()
board1.outIslandNo()
println """\
白の島は${board1.getIslandCount('□')}つ
黒の島は${board1.getIslandCount('■')}つ
"""

def board2 = new Board('''\
□■■□
□□■□
□■□□
□■■□'''
)
board2.out()
board2.search()
board2.outIslandNo()
println """\
白の島は${board2.getIslandCount('□')}つ
黒の島は${board2.getIslandCount('■')}つ
"""

/** ボードを表現するクラス */
class Board {
  /** タイル */
  def tiles
  /** コンストラクタ */
  def Board(String text) {
    tiles = text.readLines().collect{
      (it as List).collect{ color -> new Tile('color':color) }
    }
    
    this.sizeY().times { y ->
      this.sizeX().times { x ->
        this.tiles[y][x].setAround(this, y, x)
      }
    }
  }
  /** Y方向のサイズ */
  Integer sizeY() { return this.tiles.size() as Integer }
  /** X方向のサイズ */
  Integer sizeX() { return this.tiles*.size().unique().first() as Integer }
  /** ボードの未設定の島の数 */
  def remain()    { return tiles.flatten().findAll{ !it.island } }
  /** 指定された色のタイルの島数 */
  def getIslandCount(String color) {
    return tiles.flatten().findAll{ it.color == color }.collect{ it.island }.unique().size()
  }

  /** 島をサーチする */
  def search() {
    // 島番号
    Integer islandNo = 0
    // 未設定のタイル分繰り返す
    remain().each{ tile ->
      tile.island = tile.island ?: ++islandNo
      // 調べる方向
      'urdl'.each{ dir ->
        def around = tile.around[dir]
        // 周りのタイルが同じ色の場合
        if (around?.color == tile.color) {
          // 島番号が設定済み
          if (around.island) {
            tiles.flatten().findAll{ it.island == tile.island }.each{
              it.island = around.island
            }
          // 島番号が未設定
          } else {
            around.island = tile.island
          }
        }
      }
    }
  }

  // デバッグ用
  def out()         { println tiles.collect{ it*.color.join() }.join('\n') + '\n' }
  // デバッグ用
  def outIslandNo() { println tiles.collect{ it*.island.join(' ') }.join('\n') + '\n' }
}

/** タイルを表現するクラス */
class Tile {
  /** タイルの色 */
  def color = ''
  /** 周りのタイル */
  def around
  /** 島番号 */
  def island = 0

  // 周りを設定するためのクロージャ
  def closAround = { dy, dx, board, y, x ->
    def rangeY = 0..<board.sizeY()
    def rangeX = 0..<board.sizeX()
    if (rangeY.contains(y + dy) && rangeX.contains(x + dx)) {
      return board.tiles[y + dy][x + dx]
    }
  }
  // 上方向を設定するためのクロージャ
  def closAroundUp    = closAround.curry(-1,  0)
  // 右方向を設定するためのクロージャ
  def closAroundRight = closAround.curry( 0,  1)
  // 下方向を設定するためのクロージャ
  def closAroundDown  = closAround.curry( 1,  0)
  // 左方向を設定するためのクロージャ
  def closAroundLeft  = closAround.curry( 0, -1)

  /** 周りを設定する */
  def setAround(Board board, int y, int x) {
    around = [
      u:closAroundUp   (board, y, x),
      r:closAroundRight(board, y, x),
      d:closAroundDown (board, y, x),
      l:closAroundLeft (board, y, x)
    ]
  }
}

(;;)って見るからに不安だよねー あ。IEでエラーなのは気にしない方向で 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
<html><head><script>
function shima(){
  var str = "<br />", black = 0, white = 0 , cells = {};
  for(var i = 1; i <= 16; ++i){
    cells[i] = Math.floor(Math.random() * 2);
    str += (cells[i] ? "□": "■" ) + (0 == i % 4? "<br />" : ""); 
  }
  function search(){
    for(;;){
      var i = null;
      for(var cell in cells){
        i = { area: [cell], flag: cells[cell] }
        delete cells[cell];
        break;
      }
      if(!i) break;
      for(;;){
        var len = i.area.length;
        for(var j = 0; j < len; j++){
          var n = i.area[j];
          for (var cell in cells){
            cell = parseInt(cell);
            if( i.flag != cells[cell] ) continue;
            if      ( 0 == cell % 4 ){
              if( n != cell - 1 && n != cell - 4 && n != cell + 4 ) continue;
            }else if( 1 == cell % 4 ){
              if( n != cell + 1 && n != cell - 4 && n != cell + 4 ) continue;
            }else{
              if( n != cell - 1 && n != cell + 1 && n != cell - 4 && n != cell + 4 ) continue;
            }
            i.area.push(cell);
            delete cells[cell];
            break;
          }
        }
        if (len == i.area.length) break;
      }
      if(i.flag){
        white++;
      }else{
        black++;
      }
    }
  }
  search();
  document.body.innerHTML += str + "white：" + white + " black:" + black;
}
</script></head><body><button onclick="shima();">start</button></body></html>

基本的にLINQ使いで

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
    class MyMain
    {
        public static void Main(string[] args)
        {
            string island = @"
□□□□
■□■□
□□■■
□□□□
";
            Console.WriteLine(island);
            var dict = CountUpIslandNum.returnIslandNum(island);
            foreach (var key in dict.Keys)
            {
                Console.WriteLine("{0}島の数は {1}", key, dict[key]);
            }
            Console.ReadLine();
        }
    }

    class CountUpIslandNum
    {
        public static Dictionary<char, int> returnIslandNum(string island)
        {
            char[][] map = island.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries).Select(inst => inst.ToCharArray()).ToArray();
            Dictionary<char, int> countDict = new Dictionary<char, int>();
            countDict.Add('■', 0);
            countDict.Add('□', 0);
            for (int x = 0; x < map.Length; x++)
            {
                for (int y = 0; y < map[x].Length; y++)
                {
                    char c = map[x][y];
                    if (countDict.ContainsKey(c))
                    {
                        check(map, x, y, countDict[c], c);
                        countDict[c]++;
                    }
                }
            }
            return countDict;
        }
        protected static void check(char[][] map, int x, int y, int value, char block)
        {
            if (x < 0 || x >= map.Length || y < 0 || y >= map[x].Length || map[x][y] != block)
            {
                return;
            }
            map[x][y] = (char)value;
            check(map, x + 1, y, value, block);
            check(map, x - 1, y, value, block);
            check(map, x, y + 1, value, block);
            check(map, x, y - 1, value, block);
        }
    }


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
input1 = [ 0 1 1 0; 0 0 1 0; 0 1 0 0; 0 1 1 0];
input2 = [ 0 0 0 0; 1 0 1 0; 0 1 0 0; 0 0 0 0];

nBlobs1 = count_blobs(input1);
nBlobs2 = count_blobs(input2);

%以下　function　count_blobs

function nBlobs = count_blobs(input_mtx)

nBlobs = 0;
for i = 1:size(input_mtx,2)
    
    if i==1
        previous_raw = zeros(size(input_mtx,1),1)
    else
        previous_raw = input_mtx(:,i-1)
    end
    
    for j = 1:size(input_mtx,1) 
        if input_mtx(j,i) ==1 && previous_raw(j) ~=1
            if j==1 | (j > 1 && input_mtx(j-1,i) ~=1)
                    nBlobs = nBlobs+1;
            end
        end
    end

end


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$m = 4;  $n = 4;

for my $i (0 .. $m - 1) {
  for my $j (0 .. $n - 1) {
    $board[$i][$j] = int(rand 2) ? '■' : '□';
    print $board[$i][$j];
  }
  print "\n";
}
for my $i (0 .. $m - 1) {
  for my $j (0 .. $n - 1) {
    if ($board[$i][$j]) {
      $num{$board[$i][$j]}++;
      walk($i, $j, $board[$i][$j]);
    }
  }
}
print "■= $num{'■'}, □= $num{'□'}\n";

sub walk {
  my ($i, $j, $c) = @_;
  return if $c ne $board[$i][$j];
  $board[$i][$j] = 0;
  walk ($i-1, $j  , $c) if $i > 0;
  walk ($i+1, $j  , $c) if $i < $m-1;
  walk ($i  , $j-1, $c) if $j > 0;
  walk ($i  , $j+1, $c) if $j < $n-1;
}

遅くなりましたがありがとうございます。 普通のやりかたも考えたのですが、秀丸マクロはサブルーチンのネストが20階層までらしいので、マップが広がった時に対応出来ないので、この方法に至りました。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
=begin
1行読み込む毎にカウントしています。
島の数 = セル数 - 隣接している辺数 + (2x2の範囲が同色の箇所数)
例:  "wwww,bwbw,wbww,wwww"の場合、
w: 13 - 13 + 1 = 1
b: 3 - 0 + 0 = 3
=end

class Sima  
  def initialize
    @h = Hash.new(0)
    @s = []
  end
  def count(s)
    @s << s.split(//)
    @s[-1].each{|x|@h[x] += 1}
    if @s.size > 1
      count_sq(w = @s[0].zip(@s[1]), -1)
      count_sq(w.zip(w[1..-1]), 1)
      @s.shift
    end
    count_sq(@s[0].zip(@s[0][1..-1]), -1)
  end
  def count_sq(ss, delta)
    ss.each{|x|
      x.flatten!
      @h[x[0]] += delta if x.uniq.size == 1}
  end
  def all 
    @h
  end
end

[
 "wbbw,wwbw,wbww,wbbw", # => {"w"=>2, "b"=>2}
 "wwww,bwbw,wbww,wwww", # => {"w"=>1, "b"=>3}
].each{|x|
  sima = Sima.new  
  x.split(/,/).each{|i|
    sima.count(i)}
  p sima.all}


#8442 の方法が気に入ったので Haskell で。
黒のセルを 1 に、白のセルを -1 に対応させて隣接セルとの
処理を加算と除算で済ますようにしました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
{-
島の数 = セル数 - 隣接している辺数 + (2x2の範囲が同色の箇所数)
-}
import List (partition)

data BW = B | W deriving (Eq)

toInt B = 1
toInt W = -1

count xss = (n1,-n2) where
  ([n1,n2],_,_) = foldl f ([0,0],zeros,zeros) $ map (map toInt) xss
  f (ns,xs0,ys0) xs = (ns',xs,ys) where
    [ys,ys2,zs] = map g [(xs,tail xs),(xs0,xs),(ys0,ys)]
    [(bp,wp),(bn,wn)] = map (partition (>0)) [ns++xs++zs, ys++ys2]
    ns' = [sum bp - sum bn, sum wp - sum wn]
  g (as,bs) = map (`quot`2) $ zipWith (+) as bs
  zeros = repeat 0

{-
> count [[W,W,W,W],[B,W,B,W],[W,B,W,W],[W,W,W,W]]
(3,1)
-}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
=begin
#8442をruby1.9.0のEnumeratorで書き換えたものです。
=end

class Sima  
  def initialize
    @h = Hash.new(0)
  end
  def count(ss)
    ss = ss.map{|x|x.split(//)}.to_enum
    ss.each{|s|
      s.each{|x|@h[x] += 1}
      count_sq(s.each_cons(2), -1)} 
    ss.each_cons(2).each{|s|
      count_sq(w=s[0].zip(s[1]), -1)
      count_sq(w.each_cons(2), 1)}
  end
  def count_sq(ss, delta)
    ss.each{|x|
      x.flatten!
      @h[x[0]] += delta if x.uniq.size == 1}
  end
  def all 
    @h
  end
end
  
  [
   "wbbw,wwbw,wbww,wbbw", # => {"w"=>2, "b"=>2}
   "wwww,bwbw,wbww,wwww", # => {"w"=>1, "b"=>3}
   "abcc,acbc,bccc,baca", # => {"a"=>3, "b"=>3, "c"=>1}
  ].each{|x|
    sima = Sima.new  
    sima.count(x.split(/,/).to_enum)
    p sima.all}


双対グラフのオイラー標数という発想ですね。
このままですと、島に穴が開いている場合にうまくカウントができないようですので・・・
■■■
■□■
■■■
8 - 8 + 0 = 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#/usr/bin/perl
use strict;
use warnings;
use List::MoreUtils qw/uniq/;

# 天地創造
my $earth = theCreation(7,6);

my @island_groups;
my $idx = -1;
# 2次元配列をなめて、隣接する土地が同じ色の場合、グループ化する。
# ざっくりグループ化する。
for my $y (0..$#$earth){
    my $same_with_left = 0;
    for my $x (0..$#{$earth->[$y]}){
        unless($same_with_left){
            #左が違う色の場合、新しいグループをアサインする。
            $island_groups[++$idx] = [];
            push @{$island_groups[$idx]}, "$y-$x";
        }
        if($x != $#{$earth->[$y]} and $earth->[$y][$x] == $earth->[$y][$x+1]){#右と色が同じ
            $same_with_left = 1;
            my $tmp = $x+1;
            push @{$island_groups[$idx]}, "$y-$tmp";
        }
        else{
            $same_with_left = 0;
        }
        if($y != $#$earth and $earth->[$y][$x] == $earth->[$y+1][$x]){#下と色が同じ
            my $tmp = $y+1;
            push @{$island_groups[$idx]}, "$tmp-$x";
        }
    }
}

#上で作ったグループ内で重複がある場合はマージ。無くなるまで繰り返す
#例 ['1-3','2-2'] ['1-3','2,3'] => ['1-3','2-2','2-3']
while(how_many_elms(@island_groups) != +($#$earth + 1)*($#{$earth->[0]} + 1)){
    for my $i (0..$#island_groups){
        if($island_groups[$i]){
            for my $j ($i+1..$#island_groups){#積集合が存在すればマージ。後ろの集合は消去
                my @tmp = uniq(@{$island_groups[$i]}, @{$island_groups[$j]});
                if($#tmp != $#{$island_groups[$i]} + $#{$island_groups[$j]} + 1){
                    @{$island_groups[$i]} = @tmp;
                    $island_groups[$j] = [];
                }
            }
        }
    }
    @island_groups = grep {(scalar @$_) > 0} @island_groups;
}
# 結果を出力する
my ($wht_i, $blk_i) = (0,0);
for my $group (@island_groups){
    my ($x, $y) = split '-',$group->[0];
    $earth->[$x][$y] ? $blk_i++ : $wht_i++;
}
print "black: $blk_i, white: $wht_i";


###
#天地創造
sub theCreation{
    my($n, $m) = @_;
    my @result_arr;
    for my $x (1..$n){
        for my $y (1..$m){
            $result_arr[$x-1][$y-1] = int(rand(2));
            print $result_arr[$x-1][$y-1] ? '■' : '□';
        }
        print "\n";
    }
    return \@result_arr;
}
#配列の各要素が配列参照の場合、合計いくつの要素があるか。
#例： ([1,2],[33,4,5,6],[2,3,3]) => 9 が返る
sub how_many_elms{
    my @arr = @_;
    my $count = 0;
    for(@arr){
        $count += scalar @$_;
    }
    return $count;
}

F# で、Discriminated unionを使用しました。 solve [| [|0;1;1;0|];[|0;0;1;0|];[|0;1;0;0|];[|0;1;1;0|] |]として 結果は 白の島は2つ 黒の島は2つ [W1][B1][B1][W2] [W1][W1][B1][W2] [W1][B2][W2][W2] [W1][B2][B2][W2] という感じで答えが表示されます。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
type Color =
    |White
    |Black

type Piece =
    | Island of Color * Option <int>
    | Dummy
    
    member this.toStr () =
        match this with
        | Island (White,Some(n)) -> sprintf "[W%d]" n
        | Island (Black,Some(n)) -> sprintf "[B%d]" n
        | _ -> "    "
             
let makeUpArr (rawArr : int [][]) =
    let tempArr = [| for i in 0 .. (Array.length rawArr) + 1 do
                            yield (Array.create (Array.length rawArr.[0] + 2)) Dummy|]
        
    for i in 0 .. (Array.length rawArr) - 1 do
        let t = rawArr.[i]
        for j in 0 .. (Array.length rawArr.[0])-1 do
            if rawArr.[i].[j] = 0 then
                tempArr.[i+1].[j+1] <- Island(White,None)
            else 
                tempArr.[i+1].[j+1] <- Island(Black,None)
            
    tempArr
    
let mutable WhiteCount =  0
let mutable BlackCount =  0

let rec nearCheck (i0,j0) (arr: Piece [] [] ) =
    for (v1,v2) in [(1,0);(-1,0);(0,1);(0,-1)] do
        let (i1,j1) = (i0 + v1,j0 + v2) 
        match arr.[i0].[j0] ,arr.[i1].[j1] with
        |Island (c1,Some(number)),Island(c2,None) when c1 = c2 -> arr.[i1].[j1] <- Island(c1,Some(number));nearCheck(i1,j1) arr
        | _ -> ()

let check i j (arr: Piece [] [] ) =
    match arr.[i].[j] with
    |Island(c1,None) ->match c1 with
                       | White -> WhiteCount <- WhiteCount + 1; arr.[i].[j] <- Island (White,Some(WhiteCount))
                       | Black -> BlackCount <- BlackCount + 1; arr.[i].[j] <- Island (Black,Some(BlackCount))
                       nearCheck (i,j) arr
    | _ -> () 
   
let cope (arr : Piece [] []) =
 
    WhiteCount <- 0
    BlackCount <- 0
 
    for i = 1 to (Array.length arr - 2) do
        for j = 1 to (Array.length arr.[i] - 2) do
            check i j arr 

let dispResult (arr : Piece [] []) =
    printfn ""
    printfn "白の島は%dつ" WhiteCount
    printfn "黒の島は%dつ" BlackCount
    
    for i = 0 to (Array.length arr - 1) do
        for j = 0 to (Array.length arr.[i] - 1) do
            printf "%s" (arr.[i].[j].toStr()) 
        printf "\n"

let solve (rawArr : int [] [] ) =
    let data = makeUpArr rawArr
    cope data
    dispResult data

solve [| [|0;1;1;0|];[|0;0;1;0|];[|0;1;0;0|];[|0;1;1;0|] |]
solve [| [|0;0;0;0|];[|1;0;1;0|];[|0;1;0;0|];[|0;0;0;0|] |]


リンクリストを作って島を判別してます。
なるべく言語に依存しない感じに書こうとしたのですが、マップの解析とカウンター変数だけ.NETしてしまいました。
一次配列のループにしているので見辛くなっていたらすみません。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IslandCounter {
    class Program {
        static void Main() {
            string map =
@"□■□□
■□■□
□■■■
□□□□";

            int m = map.IndexOf(Environment.NewLine, 0);
            int n = map.Split(Environment.NewLine.ToCharArray(), StringSplitOptions.RemoveEmptyEntries).Length;

            map = string.Join(string.Empty, map.Split(Environment.NewLine.ToCharArray(), StringSplitOptions.RemoveEmptyEntries));
            int[] field = new int[m * n];

            Dictionary<char, int> counter = new Dictionary<char, int>();
            counter.Add('□', 0);
            counter.Add('■', 0);

            for (int i = 0; i < m * n; i++) {
                char c = map[i];
                counter[c]++;
                field[i] = i;
                if (i % m != 0) { // x軸の二行目から
                    int prev = i - 1;
                    if (c == map[prev]) {
                        field[i] = prev;
                        counter[c]--;
                    }
                }
                if (i >= m) { // y軸の二行目から
                    int prev = i - m;
                    if (c == map[prev] && GetParent(field, i) != GetParent(field, prev)) {
                        field[GetParent(field, i)] = prev;
                        counter[c]--;
                    }
                }
            }
            Console.WriteLine("白の島：" + counter['□'].ToString());
            Console.WriteLine("黒の島：" + counter['■'].ToString());
        }

        private static int GetParent(int[] field,int i) {
            int current = i;
            while (field[current] != current) {
                current = field[current];
            }
            return current;
        }
    }
}

Lost_dogです。似たような問題は、他のコンテストでも時々みかけたのでやってみました。

コーディングのポイントは、Data.Graphのcomponents関数を使うっていうだけです。モジュールって便利ですね。。

あと入力を■□に制限する必要がなかったので、若干拡張的にしてあります。

Sample Input 1

6 4
□□■□□□
■■■■■■
□■□□□□
■□□■■□

Sample Output 1

[3,4]

Sample Input 2

6 3
abbccc
aabbca
aabacb

Sample Output 2

[3,2,1]

です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
module Main where

import Prelude hiding (getLine, print)
import Data.Graph
import Data.Tree
import Data.Maybe
import Data.List
import Data.Function
import Control.Monad
import System.IO.UTF8 

main = do [w,h] <- fmap (map read.words) getLine
          xss   <- fmap (numbering w) $ replicateM h getLine
          print $ count xss $ components $ buildG (0,w*h-1) $ calEdge w xss

numbering w xss = snd $ mapAccumL f 0 xss
                  where f i xs = (i+w, zip [i..] xs)

calEdge w xss = (concatMap f xss) ++ (concatMap f $ transpose xss)
                where f (x:xs) = catMaybes $ snd $ mapAccumL g x xs
                      g (i,x) r@(j,y) | x == y    = (r,Just(i,j))
                                      | otherwise = (r,Nothing)

count xss = map length.groupBy ((==)`on`c).sortBy (compare`on`c)
            where c = snd.(concat xss!!).rootLabel

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]