bsq · Optim

▶ Aprender bsq (Optim) paso a paso · explicación de bsq

Otras versiones: Funciones

Código línea a línea

Tres columnas: el código, el trozo del subject o del main que obliga a escribir esa línea, y el por qué.

bsq.h
CódigoSubjectPor qué
#ifndef BSQ_HExpected files : *.c *.hGuarda: que el .h no se incluya dos veces.
# define BSQ_H
# define _POSIX_C_SOURCE 200809LgetlineSin esto getline no se declara con -std=c99/flags estrictos. Antes de cualquier include.
# include <stdio.h>fopen, fclose,
getline, fscanf, fputs		FILE, fopen, getline, fscanf, fputs.
# include <stdlib.h>malloc, calloc, realloc, freecalloc y free.
typedef struct s_mapThe first line of the map contains information on how to read the mapTodo el mapa en un struct: cabecera + filas.
{
int rows;The number of lines on the map;Número de filas (de la cabecera).
int cols;All lines must have the same length.Ancho: lo marca la primera fila.
char empty;The "empty" character;Carácter vacío.
char obst;The "obstacle" character;Carácter obstáculo.
char full;The "full" character.Carácter con el que pinto el cuadrado.
char **grid;Las filas: un array de strings.
} t_map;Nombre corto del struct.
#endifFin de la guarda.
bsq.c
CódigoSubjectPor qué
#include "bsq.h"El .c usa el struct del .h.
// ---------- memoria ----------
void free_map(t_map *m)Libera todo lo que haya, esté el mapa bien o mal.
{
if (!m->grid)Si no llegó a reservar filas…
return ;…nada que liberar.
for (int i = 0; i < m->rows; i++)Cada fila.
free(m->grid[i]);free(NULL) no hace nada: las filas no leídas siguen a NULL por el calloc.
free(m->grid);Y el array de filas.
}
// ---------- lectura y validación ----------
// Primera línea: "9 . o x" (o "9.ox"). Devuelve 1 si es válida.
int read_header(FILE *f, t_map *m)The first line of the map contains information on how to read the map (space separated) :Primera línea: "9 . o x". Devuelve 1 si vale.
{
char *rest = NULL;Para getline: NULL y 0 → que reserve ella.
size_t cap = 0;
if (fscanf(f, "%d %c %c %c", &m->rows, &m->empty, &m->obst, &m->full) != 4)The number of lines on the map;Un número y tres caracteres. El espacio en el formato se come los espacios (o ninguno: "9.ox" también vale). Si no lee 4 → error.
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
int ok = getline(&rest, &cap, f) > 0; // se come el '\n' que quedaAt each end of line, there's a line break.fscanf deja el '\n' sin leer: me lo como con getline para que la fila 0 empiece limpia.
free(rest);getline reservó memoria: libero.
if (!ok || m->rows <= 0)There's at least one line of at least one box.Sin salto de línea o sin filas → error.
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
if (m->empty == m->obst || m->empty == m->full || m->obst == m->full)or if two characters (of empty, full and obstacle) are identical.Los tres caracteres distintos.
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
return (1);Todo bien → 1.
}
// Lee la fila i, le quita el '\n' y la guarda. Devuelve 1 si es válida.
int read_row(FILE *f, t_map *m, int i)All lines must have the same length.Lee la fila i, le quita el '\n' y comprueba que vale.
{
char *line = NULL;Para getline: que reserve ella.
size_t cap = 0;
int len = getline(&line, &cap, f);getlineLee una línea entera con su '\n'. Devuelve la longitud, o -1 al final.
m->grid[i] = line; // guardada ya: free_map la libera siempreLa guardo antes de validar: así, falle lo que falle, free_map la libera.
if (len <= 1 || line[len - 1] != '\n') // fin del fichero, fila vacía o sin '\n'At each end of line, there's a line break.Fin del fichero, fila vacía ("\n"), o última sin '\n' → error.
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
len--;Ya sé que el último es '\n'…
line[len] = '\0';…lo quito.
if (i == 0)Primera fila…
m->cols = len; // la primera fila marca el anchoAll lines must have the same length.…marca el ancho.
if (len != m->cols)All lines must have the same length.Distinto ancho → error.
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
for (int j = 0; j < len; j++)Cada carácter.
if (line[j] != m->empty && line[j] != m->obst)The characters on the map can only be those introduced in the first line.Solo vacío u obstáculo (el full no puede venir en el mapa).
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
return (1);Todo bien → 1.
}
int read_map(FILE *f, t_map *m)A file containing the map will be provided.Cabecera + todas las filas. 1 si todo vale.
{
if (!read_header(f, m))Cabecera mala → error.
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
m->grid = calloc(m->rows, sizeof(char *)); // todas las filas empiezan a NULLcalloccalloc y no malloc: todas a NULL, así free_map puede liberar un mapa a medias.
if (!m->grid)Si no llegó a reservar filas…
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
for (int i = 0; i < m->rows; i++)Cada fila.
if (!read_row(f, m, i))Una fila mala → error, sin seguir.
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
return (1);Todo bien → 1.
}
// ---------- el algoritmo ----------
int min3(int a, int b, int c)El menor de tres.
{
int min = a;
if (b < min)
min = b;
if (c < min)
min = c;
return (min);
}
// size[i][j] = lado del mayor cuadrado vacío cuya esquina de ABAJO A LA DERECHA es (i, j)
void solve(t_map *m)The aim of this program is to find the biggest square on a map, avoiding obstacles.El algoritmo: una pasada rellenando size, luego pinto.
{
int size[m->rows][m->cols];Array en la pila del tamaño del mapa (VLA de C99): nada que liberar.
int best = 0;Lado del mejor cuadrado.
int top = 0;Su fila de arriba.
int left = 0;Su columna izquierda.
for (int i = 0; i < m->rows; i++)Cada fila.
{
for (int j = 0; j < m->cols; j++)Cada columna.
{
if (m->grid[i][j] == m->obst)avoiding obstaclesObstáculo → ningún cuadrado acaba aquí.
size[i][j] = 0;
else if (i == 0 || j == 0)Primera fila o columna: como mucho un cuadrado de 1.
size[i][j] = 1;
else
size[i][j] = 1 + min3(size[i - 1][j], size[i][j - 1], size[i - 1][j - 1]);the biggest square possibleLa clave: 1 + el menor de arriba, izquierda y diagonal. El más pequeño de los tres limita.
if (size[i][j] > best) // '>' y no '>=': en empate gana el primeroclosest to the top of the map, then the one that's most to the left.> estricto: recorro de arriba a abajo y de izquierda a derecha, así en empate se queda el primero.
{
best = size[i][j];Nuevo mejor.
top = i - best + 1; // esquina de ARRIBA A LA IZQUIERDA(i, j) es la esquina de abajo a la derecha: resto para sacar la de arriba.
left = j - best + 1;
}
}
}
for (int i = top; i < top + best; i++)replace '"empty" characters' by '"full" characters'Pinto el cuadrado.
for (int j = left; j < left + best; j++)
m->grid[i][j] = m->full;
}
// ---------- programa ----------
void print_map(t_map *m)Imprime las filas.
{
for (int i = 0; i < m->rows; i++)Cada fila.
{
fputs(m->grid[i], stdout);fputsLa fila, sin '\n' (se lo quité al leer)…
fputs("\n", stdout);…y se lo vuelvo a poner.
}
}
void bsq(FILE *f)Un mapa entero: leer, resolver, imprimir, liberar.
{
t_map m = {0};Todo a 0: grid NULL, así free_map no libera basura.
if (read_map(f, &m))Si el mapa vale…
{
solve(&m);
print_map(&m);
}
else
fputs("map error\n", stderr);your program should display "map error" on the error output followed by a line break.Si no: a stderr.
free_map(&m);Libero siempre, haya ido bien o mal.
}
int main(int argc, char **argv)
{
if (argc == 1)Should there be no passed arguments, your program must be able to read on the standard input.Sin argumentos…
bsq(stdin);…leo de la entrada estándar.
for (int i = 1; i < argc; i++)Your program will then move on to the next map.Cada fichero, aunque uno falle.
{
FILE *f = fopen(argv[i], "r");fopen
if (!f)No se puede abrir → map error.
fputs("map error\n", stderr);your program should display "map error" on the error output followed by a line break.Si no: a stderr.
else
{
bsq(f);
fclose(f);fclose
}
if (argc > 2)When your program receives more than one map in argument, each solution or "map error" must be followed by a line break.Con más de un mapa, un salto de línea tras cada uno.
fputs("\n", stdout);…y se lo vuelvo a poner.
}
return (0);In case of an invalid map, your program should display "map error" on the error output followed by a line break.Mal → 0.
}