創造工学演習の予備実験 part 2 として、Flood Fill , 8queen にチャレンジしてみる。

Flood fill アルゴリズム

前の問題は、今年度のプログラミングコンテストの課題のパズルとは、方向性が違うので、今年度のプロコンの競技部門にちょっとだけ近い2次元フィールドのパズルネタで演習。(Wikipedia Flood-fill参照)

以下の image のような2次元配列が与えられたら、指定座標(x,y)を中心に周囲を塗りつぶす処理を作成せよ。

include <stdio.h>

// *は壁 SPCは白 この領域の指定位置を#で塗りつぶす。                            
char image1[10][10] = { // (4,4)始点で塗りつぶし後
        "*********" ,   // ********* 
        "*   *   *" ,   // *   *###*
        "*   *   *" ,   // *   *###*
        "*  *    *" ,   // *  *####*
        "***   ***" ,   // ***###***
        "*    *  *" ,   // *####*  *
        "*   *   *" ,   // *###*   *
        "*   *   *" ,   // *###*   *
        "*********" ,   // *********
} ;

char image2[10][10] = { // 応用問題用の画像例
        "*********" ,   //  *   のような隙間は通り抜けられる
        "*   *   *" ,   // *    ようにするにはどうすればいい？
        "*  **   *" ,   //   **
        "* **    *" ,   //  **  これは通り抜けられない
        "***   ***" ,   // **
        "*    *  *" ,
        "*   *   *" ,
        "*   *   *" ,
        "*********" ,
} ;

// 盤面を表示                                                                   
void print_image( char image[10][10] ) {
  for( int y = 0 ; y < 9 ; y++ ) {
    for( int x = 0 ; x < 9 ; x++ ) {
      printf( "%c" , image[y][x] ) ;
    }
    printf( "\n" ) ;
  }
}

// 再帰呼び出しを使った flud_fill アルゴリズム                                  
void flood_fill( char image[10][10] , int x , int y , char fill ) {
  // image: 塗りつぶす画像
  // x,y:   塗りつぶす場所
  // fill:  書き込む文字
  // 指定座標が空白なら
  if ( image[y][x] == ' ' ) {
    // その座標を埋める
    image[y][x] = fill ;
    //////////////////////////////////////
    // ここに周囲をflud_fillする処理を書く  //
    ////////////////////////////////////// 
  }
}

int main() {
  print_image( image1 ) ;
  flood_fill( image1 , 4 , 4 , '#' ) ;
  print_image( image1 ) ;
  return 0 ;
}

import java.util.*;

public class Main {
    public static String[] image1 = {
        "*********" ,   // ********* 
        "*   *   *" ,   // *   *###*
        "*   *   *" ,   // *   *###*
        "*  *    *" ,   // *  *####*
        "***   ***" ,   // ***###***
        "*    *  *" ,   // *####*  *
        "*   *   *" ,   // *###*   *
        "*   *   *" ,   // *###*   *
        "*********" ,   // *********
    } ;
    // 文字配列を文字の2次元配列に変更
    public static char[][] map_from_string( String[] image ) {
        char[][] map = new char[ image.length ][ image[0].length() ] ;
        for( int i = 0 ; i < image.length ; i++ ) {
            for( int j = 0 ; j < image[ i ].length() ; j++ ) {
                map[ i ][ j ] = image[ i ].charAt( j ) ;
            }
        }
        return map ;
    }
    // 2次元配列を出力
    public static void print_image( char[][] map ) {
        for( int i = 0 ; i < map.length ; i++ ) {
            for( int j = 0 ; j < map[i].length ; j++ ) {
                System.out.print( map[ i ][ j ] ) ;
            }
            System.out.println() ;
        }
    }
    // 塗りつぶし処理
    public static void flood_fill( char[][] map , int x , int y , char c ) {
        if ( map[x][y] == ' ' ) {

            // 指定された場所に埋める文字を代入
            map[x][y] = c ;

            ////////////////////////////////////////////
            // ここに周囲を flood_fill する処理を書く //
            ////////////////////////////////////////////
        }
    }
    public static void main(String[] args) throws Exception {
        char[][] map = map_from_string( image1 ) ;
        print_image( map ) ;
        flood_fill( map , 4 , 4 , '#' ) ;
        print_image( map ) ;
    }
}

• Flood Fill Java版(Paiza.io)

応用問題

Wikipediaのflood-fill のプログラムの説明のアルゴリズムでは、左図黒のような斜めに並んだブロックは、境界として通り抜けられないようにつくられている。

そこで、斜めに並んだブロックは通り抜けられるルールとした場合のプログラムを記述せよ。

レポート提出

レポートでは、指定長を辺の組み合わせで作るテーマか、Flood-fill のテーマのいずれかにて、以下の内容をまとめてレポートとして提出すること。

• • レポートの説明(自分の選んだテーマと自分なりの説明)
  • プログラムリスト
  • 動作確認の結果

N Queen

パズル問題の定番の8 Queen を考えてみる。

8 Queen とは、8×8のチェスの盤面に、8つの Queen をお互いに取られないように配置するパズル。

import java.util.*;

public class Main {
    public final static int size = 4 ;
    public static int[] board = new int[ size ] ;
    
    // できあがった盤面を表示する補助関数
    public static void print_board( int[] board ) {
        for( int i = 0 ; i < size ; i++ ) {
            for( int j = 0 ; j < board[ i ] ; j++ )
                System.out.print( "+ " ) ;
            System.out.print( "Q " ) ;
            for( int j = board[ i ] + 1 ; j < size ; j++ )
                System.out.print( "+ " ) ;
            System.out.println() ;
        }
        System.out.println() ;
    }
    
    // n_queen本体
    //   4 queen の boad 配列
    //   [ 1 3 0 2 ]
    //     + + Q +
    //     Q + + +
    //     + + + Q
    //     + Q + +
    public static void n_queen( int[] board , int n , int i ) {
        // nは盤面の大きさ
        // i列目のj行目に置く(i=2)
        // [ 1 3 j ? ]
        //   0 1 2 3
        // 0 + + + +
        // 1 Q + + +
        // 2 + +[Q]+ j=2
        // 3 + Q + +
        if ( i == n ) {
            // 右端まですべて埋まったら答えとして表示
            print_board( board ) ;
        } else {
            // j行目に置くのを試す
            for( int j = 0 ; j < size ; j++ ) {
                // 同じ行に置かれたものが無いか探す
                boolean flag = true ;
                for( int k = 0 ; k < i && flag ; k++ ) {
                    if ( board[ k ] == j )
                        flag = false ; // 同じ行にすでに置かれている
                }
                if ( flag ) {   // 同じ行が使われていなければ
                    // 斜め左上に向かってぶつかるQueenを探す
                    for( int u = j - 1 , h = i - 1 ; u >= 0 && h >= 0 && flag ; u-- , h-- ) {
                       if ( board[ h ] == u )
                            flag = false ;
                    }
                    // 斜め左下に向かってぶつかるQueenを探す
                    for( int d = j + 1 , h = i - 1 ; d < size && h >= 0 && flag ; d++ , h-- ) {
                        if ( board[ h ] == d )
                            flag = false ;
                    }
                    if ( flag ) {
                        // 左横、左斜め上、左斜め下にぶつかるQueenが無かったら、再帰
                        board[ i ] = j ;
                        n_queen( board , n , i + 1 ) ;
                    }
                }
            } 
        }
    }
    public static void main(String[] args) throws Exception {
        n_queen( board , size , 0 ) ;
        print_board( board ) ;
        
    }
}

• N Queen(Paiza.io)