bsq · Funciones

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

Otras versiones: Optim

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.
typedef struct s_squarethe biggest square possibleEl cuadrado encontrado: lado y esquina.
{
int size;Lado.
int top;Fila de arriba.
int left;Columna izquierda.
} t_square;Nombre corto del struct.
#endifFin de la guarda.
bsq.c
CódigoSubjectPor qué
#include "bsq.h"El .c usa el struct del .h.
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;
int ok;Si la cabecera vale.
ok = fscanf(f, "%d %c %c %c",The number of lines on the map;Un número y tres caracteres, separados por espacios.
&m->rows, &m->empty, &m->obst, &m->full) == 4;Tienen que salir los 4.
ok = ok && getline(&rest, &cap, f) == 1;At each end of line, there's a line break.Lo que queda de la línea tiene que ser solo el '\n'.
free(rest);getline reservó memoria: libero.
return (ok && m->rows > 0 && m->empty != m->obstThere's at least one line of at least one box.Al menos una fila…
&& m->empty != m->full && m->obst != m->full);or if two characters (of empty, full and obstacle) are identical.…y los tres caracteres distintos.
}
int valid_chars(t_map *m, char *line)The characters on the map can only be those introduced in the first line.1 si la fila solo tiene vacío u obstáculo.
{
for (int j = 0; line[j]; j++)Cada carácter hasta el '\0'.
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_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;La guardo antes de validar: así, falle lo que falle, free_map la libera.
if (len <= 1 || line[len - 1] != '\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.
line[--len] = '\0';Quito el '\n' y la longitud baja en 1.
m->cols = i ? m->cols : len;All lines must have the same length.La primera fila marca el ancho.
return (len == m->cols && valid_chars(m, line));All lines must have the same length.Mismo ancho y caracteres válidos.
}
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 *));calloccalloc y no malloc: todas las filas 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.
}
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);
}
int cell_size(t_map *m, int i, int j, int size[][m->cols])the biggest square possibleLado del mayor cuadrado cuya esquina de abajo a la derecha es (i, j).
{
if (m->grid[i][j] == m->obst)avoiding obstaclesObstáculo → ningún cuadrado acaba aquí.
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 (i == 0 || j == 0)Primera fila o columna: como mucho un cuadrado de 1.
return (1);Todo bien → 1.
return (1 + min3(size[i - 1][j], size[i][j - 1], size[i - 1][j - 1]));La clave: 1 + el menor de arriba, izquierda y diagonal.
}
t_square square_ending_at(int i, int j, int s)El cuadrado de lado s que acaba en (i, j).
{
return ((t_square){s, i - s + 1, j - s + 1});Resto para sacar la esquina de arriba a la izquierda.
}
t_square find_square(t_map *m)The aim of this program is to find the biggest square on a map, avoiding obstacles.Una pasada rellenando size y me quedo con el mayor.
{
int size[m->rows][m->cols];Array en la pila del tamaño del mapa (VLA de C99): nada que liberar.
t_square best = {0, 0, 0};De momento, ninguno.
for (int i = 0; i < m->rows; i++)Cada fila.
for (int j = 0; j < m->cols; j++)Cada columna.
{
size[i][j] = cell_size(m, i, j, size);Relleno la casilla con lo de arriba e izquierda, ya calculado.
if (size[i][j] > best.size)closest to the top of the map, then the one that's most to the left.> estricto: en empate gana el que vi antes (arriba, luego izquierda).
best = square_ending_at(i, j, size[i][j]);Nuevo mejor.
}
return (best);
}
void fill_square(t_map *m, t_square sq)replace '"empty" characters' by '"full" characters'Pinto el cuadrado.
{
for (int i = sq.top; i < sq.top + sq.size; i++)Sus filas…
for (int j = sq.left; j < sq.left + sq.size; j++)…y sus columnas.
m->grid[i][j] = m->full;
}
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 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.
}
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…
{
fill_square(&m, find_square(&m));Buscar el cuadrado y pintarlo.
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.
}
void bsq_file(char *path)A file containing the map will be provided.Un fichero: abrir, resolver, cerrar.
{
FILE *f = fopen(path, "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
}
}
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.
{
bsq_file(argv[i]);Your program will then move on to the next map.Cada fichero, aunque uno falle.
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.
}