EXAM DRILL 1.0
読み取り中…
検索中…
一致する文字列を見つけられません
bsq_solver.c
1#include "bsq.h"
2
3// 補助関数: 3つの数値の最小値を返す
4static int ft_min(int a, int b, int c) {
5 int min = a;
6 if (b < min)
7 min = b;
8 if (c < min)
9 min = c;
10 return (min);
11}
12
72t_square find_largest_square(t_map *map) {
73 int **dp;
74 int i, j;
75 t_square largest_square = {0, 0, 0};
76
77 if (!map || !map->data || map->info.rows == 0 || map->info.cols == 0)
78 return (largest_square);
79
80 // DPテーブルの初期化
81 dp = (int **)malloc(sizeof(int *) * map->info.rows);
82 if (!dp)
83 return (largest_square);
84 i = 0;
85 while (i < map->info.rows) {
86 dp[i] = (int *)malloc(sizeof(int) * map->info.cols);
87 if (!dp[i]) {
88 while (--i >= 0)
89 free(dp[i]);
90 free(dp);
91 return (largest_square);
92 }
93 i++;
94 }
95
96 // 最初の行と列を初期化
97 i = 0;
98 while (i < map->info.rows) {
99 if (map->data[i][0] == map->info.empty)
100 dp[i][0] = 1;
101 else
102 dp[i][0] = 0;
103 // 最大の正方形の初期値を設定
104 if (dp[i][0] > largest_square.size) {
105 largest_square.size = dp[i][0];
106 largest_square.x = 0;
107 largest_square.y = i;
108 }
109 i++;
110 }
111
112 j = 1;
113 while (j < map->info.cols) {
114 if (map->data[0][j] == map->info.empty)
115 dp[0][j] = 1;
116 else
117 dp[0][j] = 0;
118 // 最大の正方形の初期値を設定
119 if (dp[0][j] > largest_square.size) {
120 largest_square.size = dp[0][j];
121 largest_square.x = j;
122 largest_square.y = 0;
123 }
124 j++;
125 }
126
127 // DPテーブルを埋める
128 i = 1;
129 while (i < map->info.rows) {
130 j = 1;
131 while (j < map->info.cols) {
132 if (map->data[i][j] == map->info.obstacle)
133 dp[i][j] = 0;
134 else
135 dp[i][j] = ft_min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
136
137 // 最大の正方形を更新（上、左を優先）
138 // 問題文の要件: "If there's more than one solution, we'll choose the one
139 // that is closest to the top and then to the left."
140 if (dp[i][j] > largest_square.size) {
141 largest_square.size = dp[i][j];
142 largest_square.x = j - largest_square.size + 1; // 左上のx座標
143 largest_square.y = i - largest_square.size + 1; // 左上のy座標
144 } else if (dp[i][j] == largest_square.size) {
145 // 同じサイズの正方形が見つかった場合、上、左を優先
146 // このロジックでは i (y) が小さい順に探索しているため、
147 // 同一行内であれば j (x) が小さいものが先に見つかるが、
148 // 行が進むと y が大きくなる。
149 // したがって、単に >
150 // で更新すれば、より上・左にあるものが保持され続けるはずだが、
151 // 念のため座標比較を行う（または、単に無視しても良いかもしれないが、厳密には要確認）
152 // ただし、このループ順序 (i=1..rows, j=1..cols) だと、
153 // 新しい dp[i][j] は常に「より下」または「同じ行でより右」にある。
154 // したがって、同じサイズなら更新しなければ (= > のみを使えば)、
155 // 自動的に「一番上かつ一番左」のもの（最初に見つけたもの）が残る。
156 // ※初期化ループで見つけたものと比較する場合は注意が必要だが、
157 // 基本的には「更新しない」が正解。
158
159 // 念のため座標ベースで比較
160 int current_x = j - dp[i][j] + 1;
161 int current_y = i - dp[i][j] + 1;
162
163 // 既存の largest_square は常に「これまでに見つけた中で最適」なもの
164 // 新しい候補 (current) が 既存 (largest) より 上(y小) または
165 // 同じyで左(x小) なら更新 しかしループ順序的に current_y >=
166 // largest_square.y は確定
167 if (current_y < largest_square.y ||
168 (current_y == largest_square.y && current_x < largest_square.x)) {
169 largest_square.x = current_x;
170 largest_square.y = current_y;
171 }
172 }
173 j++;
174 }
175 i++;
176 }
177
178 // DPテーブルのメモリを解放
179 i = 0;
180 while (i < map->info.rows) {
181 free(dp[i]);
182 i++;
183 }
184 free(dp);
185
186 return (largest_square);
187}
188
210void print_solution(t_map *map, t_square square) {
211 int i, j;
212
213 if (!map || !map->data || square.size == 0) {
214 // 正方形が見つからなかった場合、元のマップを出力
215 i = 0;
216 while (i < map->info.rows) {
217 ft_putstr_fd(map->data[i], STDOUT_FILENO);
218 ft_putstr_fd("\n", STDOUT_FILENO);
219 i++;
220 }
221 return;
222 }
223
224 i = 0;
225 while (i < map->info.rows) {
226 j = 0;
227 while (j < map->info.cols) {
228 if (i >= square.y && i < square.y + square.size && j >= square.x &&
229 j < square.x + square.size)
230 write(STDOUT_FILENO, &map->info.full, 1);
231 else
232 write(STDOUT_FILENO, &map->data[i][j], 1);
233 j++;
234 }
235 write(STDOUT_FILENO, "\n", 1);
236 i++;
237 }
238}
ft_putstr_fd
void ft_putstr_fd(const char *s, int fd)
文字列をファイルディスクリプタに書き込む
Definition ft_utils.c:10
print_solution
void print_solution(t_map *map, t_square square)
解決策をマップに適用し、結果を出力する
Definition bsq_solver.c:210
find_largest_square
t_square find_largest_square(t_map *map)
動的計画法 (DP) を使用して最大の正方形を見つける
Definition bsq_solver.c:72
s_map_info::empty
char empty
空き地を表す文字
Definition bsq.h:97
s_map_info::obstacle
char obstacle
障害物を表す文字
Definition bsq.h:98
s_map_info::full
char full
正方形を埋める文字
Definition bsq.h:99
s_map_info::rows
int rows
マップの行数
Definition bsq.h:96
s_map_info::cols
int cols
マップの列数 (最初のデータ行を読んでから決定)
Definition bsq.h:100
s_map
マップ全体の状態を保持する構造体
Definition bsq.h:106
s_map::data
char ** data
マップデータ（2次元配列）。data[row][col] でアクセス
Definition bsq.h:108
s_map::info
t_map_info info
マップの設定情報
Definition bsq.h:107
s_square
見つかった最大の正方形の解を格納する構造体
Definition bsq.h:114
s_square::x
int x
正方形の左上のx座標 (0-indexed)
Definition bsq.h:115
s_square::size
int size
正方形の一辺の長さ
Definition bsq.h:117
s_square::y
int y
正方形の左上のy座標 (0-indexed)
Definition bsq.h:116