BSQプログラムのエントリポイント

練習の要点

• コマンドライン引数の有無による分岐処理。
• 複数ファイル処理時の出力フォーマット制御（空行の挿入）。
• main 関数から各モジュールへの適切な委譲。

実行フロー

1. 引数なし (argc == 1):
   • 標準入力 (stdin) に対して solve_single_map() を実行。
2. 引数あり (argc > 1):
   • ループで各引数（ファイルパス）を処理。
   • 2つ目以降のマップ処理前には改行を出力。
   • fopen() でファイルを開き、成功すれば solve_single_map()。
   • 失敗すれば ft_error() ("map error")。
   • ファイルを fclose() で閉じる。

引数

[in]	argc	引数の数
[in]	argv	引数の配列

戻り値

常に 0 (仕様によりエラー時も終了コードは問われないが、通常は0)

main.c の 64 行目に定義があります。

単一のマップを処理する

指定されたファイルストリームからマップを読み込み、最大正方形を探索して結果を表示する。

実行フロー

1. load_map(): ストリームからマップ構造体を生成。
2. エラーチェック: 生成失敗なら ft_error()。
3. find_largest_square(): 最大正方形を探索。
4. print_solution(): 結果を出力。
5. free_map(): メモリ解放。

実装のステップ

1. load_map() を呼び出し、戻り値の t_map* を受け取る。
2. 返り値が NULL の場合、マップエラー ("map error") を出力して関数を終了する (return)。
3. find_largest_square() を呼び出し、解 (t_square) を取得する。
4. print_solution() を呼び出し、解を反映したマップを出力する。
5. free_map() を呼び出し、使用したメモリをクリーンアップする。

引数

[in]

stream

読み込み元のファイルストリーム (stdin または ファイル)

main.c の 26 行目に定義があります。

マップ全体をロードする

parse_map_header() と read_map_data() を組み合わせて、ストリームから完全なマップ構造体を生成する。

実装のステップ

1. t_map 構造体のメモリを確保し、ゼロ初期化する。
2. getline() で1行目を読み込み、parse_map_header() に渡してメタデータを解析する。
3. 解析に成功したら、read_map_data() を呼び出して残りのデータを読み込む。
4. どの段階でも失敗したら、確保したメモリを free_map() 等で解放し、NULL を返す。

引数

[in]

stream

読み込み元のファイルストリーム

戻り値

成功なら確保された t_map へのポインタ、失敗なら NULL

map_parser.c の 192 行目に定義があります。

マップの最初の行を解析する

最初の行（例: "9.ox" または "9 . o x"）から、行数、空き地文字、障害物文字、埋まり文字を抽出する。

実装のステップ

1. 文字列の末尾からスキャンを開始し、改行やスペースをスキップする。
2. 後ろから順に full, obstacle, empty の3つの文字を取得する。
3. 残りの先頭部分を行数とみなす。
4. バリデーション:
   • 3つの文字が取得できているか。
   • 行数部分が正の整数であり、数値として妥当か。
   • 文字の重複がなく、印刷可能文字であるか。
5. すべてのチェックを通過した場合、info 構造体に値を設定し、1 を返す。

引数

[in]	first_line	解析対象の文字列
[out]	info	結果を格納する構造体へのポインタ

戻り値

成功なら 1、失敗なら 0

map_parser.c の 24 行目に定義があります。

マップデータを読み込む

ヘッダー以降の行を読み込み、2次元配列としてメモリに格納する。

実装のステップ

1. マップの行数分 (info->rows) だけループし、getline() で行を読み込む。
2. 列数のチェック:
   • 最初のデータ行で、改行を除いた長さを info->cols として記録する。
   • 2行目以降は、長さが info->cols と一致するか確認する。不一致ならエラー。
3. メモリ確保: 各行に対して malloc() し、文字列をコピーする (strncpy() 等)。
4. 文字のバリデーション:
   • 各文字が empty または obstacle のいずれかであることを確認する。
   • 未定義の文字が含まれていればエラー。
5. 行数が宣言通り (info->rows) 読み込めなければエラー。
6. 失敗時は、確保済みのメモリをすべて解放してから 0 を返す。

引数

[in]	stream	読み込み元のファイルストリーム
[in,out]	map	情報を格納する t_map 構造体 (rows, chars 設定済み)

戻り値

成功なら 1、失敗なら 0

map_parser.c の 114 行目に定義があります。

マップのメモリを解放する

t_map 構造体と、そのメンバである2次元配列 data を安全に解放する。

実装のステップ

1. ポインタが NULL でないか確認する。
2. data が存在すれば、各行 (data[i]) をループで free() する。
3. 配列自体 (data) を free() する。
4. 最後に構造体 (map) を free() する。

引数

[in]

map

解放するマップ構造体へのポインタ

map_parser.c の 244 行目に定義があります。

動的計画法 (DP) を使用して最大の正方形を見つける

マップを走査し、各地点を右下とする最大正方形のサイズを計算する。

アルゴリズムの概要

• dp[i][j] は、(i, j) を右下角とする正方形の最大サイズを表す。
• 漸化式:
  • 障害物の場合: dp[i][j] = 0
  • 空き地の場合: dp[i][j] = ft_min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

実装のステップ

1. エラー処理: マップが無効、または行・列が0の場合は初期値 (all 0) を返す。
2. メモリ確保: dp テーブル（int**）を行数分確保し、各行を列数分確保する。
3. 初期化:
   • 1行目 (i=0) と 1列目 (j=0) をスキャン。
   • 空き地なら 1、障害物なら 0 を設定。
   • この段階で最大値 (largest_square) を更新する可能性があるためチェックを入れる。
4. DP計算:
   • i=1, j=1 から開始する二重ループ。
   • 障害物なら 0。
   • 空き地なら、「上」「左」「左上」の最小値 + 1。
5. 最大値の更新:
   • 現在の dp[i][j] が largest_square.size より大きい場合、更新する。
   • size が同じ場合、**「より上、そしてより左」** のものを優先するロジックを実装する。
6. free(): 計算が終わったら dp テーブルを解放する。
7. 見つかった最大正方形の情報を返す。

PlantUML フローチャート

引数

[in]

map

処理対象のマップ構造体

戻り値

見つかった最大の正方形の情報 (t_square)

bsq_solver.c の 72 行目に定義があります。

解決策をマップに適用し、結果を出力する

特定された最大の正方形エリアを full 文字で埋め、マップ全体を標準出力に書き出す。

実装のステップ

1. 例外処理: 正方形が見つからなかった場合（size == 0）、マップをそのまま出力して終了。
2. 二重ループでマップの全セルを走査。
3. 現在の座標 (i, j) が正方形の範囲内にあるか判定する。
   • square.y <= i < square.y + square.size
   • square.x <= j < square.x + square.size
4. 範囲内であれば full 文字を出力。
5. 範囲外であれば元の文字を出力。
6. 各行の終わりに改行を出力。

引数

[in]	map	マップ構造体
[in]	square	適用する正方形の情報

bsq_solver.c の 210 行目に定義があります。

文字列をファイルディスクリプタに書き込む

引数

[in]	s	書き込む文字列 (NULL安全)
[in]	fd	書き込み先のファイルディスクリプタ

ft_utils.c の 10 行目に定義があります。

エラーメッセージ標準エラー出力に出力し、改行する

引数

[in]

msg

出力するエラーメッセージ (NULL安全)

ft_utils.c の 21 行目に定義があります。