bsq

Código comentado línea a línea y paso a paso:

• Optim · paso a paso
• Funciones · paso a paso

Entregas: bsq.h, bsq.c. Flags: gcc -Wall -Wextra -Werror

Qué pide (en palabras normales)

• Te dan un mapa con casillas vacías (.) y obstáculos (o).
• Buscas el cuadrado más grande de casillas vacías y lo pintas con el carácter lleno (x).
• Si hay empate: el de más arriba, y si sigue el empate, el de más a la izquierda.
• La primera línea dice cómo leer el mapa: 9 . o x = 9 líneas, vacío ., obstáculo o, lleno x.
• Mapas por argumento (uno o varios). Sin argumentos → lee de stdin.
• Mapa mal → map error por la salida de error, y sigue con el siguiente.

Assignment name              : bsq
Expected files               : *.c *.h
Allowed functions and globals: malloc, calloc, realloc, free, fopen, fclose,
getline, fscanf, fputs, fprintf, stderr, stdout, stdin, errno
--------------------------------------------------------------------------------

The aim of this program is to find the biggest square on a map, avoiding obstacles.
A file containing the map will be provided. It'll have to be passed as an argument for your program.
The first line of the map contains information on how to read the map (space separated) :
 - The number of lines on the map;
 - The "empty" character;
 - The "obstacle" character;
 - The "full" character.
The map is made up of '"empty" characters', lines and '"obstacle" characters'.
The aim of the program is to replace '"empty" characters' by '"full" characters' in order to represent the biggest square possible.
In the case that more than one solution exists, we'll choose to represent the square that's closest to the top of the map, then the one that's most to the left.
When your program receives more than one map in argument, each solution or "map error" must be followed by a line break.
Should there be no passed arguments, your program must be able to read on the standard input.

Definition of a valid map :
 - All lines must have the same length.
 - There's at least one line of at least one box.
 - At each end of line, there's a line break.
 - The characters on the map can only be those introduced in the first line.
 - The map is invalid if a character is missing from the first line, or if two characters (of empty, full and obstacle) are identical.
 - The characters can be any printable character, even numbers.
 - In case of an invalid map, your program should display "map error" on the error output followed by a line break. Your program will then move on to the next map.

example:
%>cat example_file
9 . o x
...........................
....o......................
............o..............
...........................
....o......................
...............o...........
...........................
......o..............o.....
..o.......o................
%>./bsq example_file
.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxxo..............
.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxx...o...........
.....xxxxxxx...............
......o..............o.....
..o.......o................
%>

Vídeos

El algoritmo sobre un mapa de ejemplo, con el código escribiéndose en tiempo real.

Optim, paso a paso

Partido en funciones

4 piezas

1. Primera línea con fscanf

if (fscanf(f, "%d %c %c %c", &m->rows, &m->empty, &m->obst, &m->full) != 4)
	return (0);
int	ok = getline(&rest, &cap, f) > 0;	// se come el '\n' que queda

%d = un número, %c = un carácter. Devuelve cuántos leyó: tienen que ser 4. fscanf deja el '\n' sin leer: un getline se come el resto de la línea para que la primera fila empiece limpia.

2. Cada línea con getline

char	*line = NULL;
size_t	cap = 0;
int		len = getline(&line, &cap, f);

m->grid[i] = line;	// guardada ya: free_map la libera siempre

Puntero a NULL + cap = 0 → getline reserva la memoria él solo. Lee la línea con su \n y devuelve cuántos caracteres leyó (-1 si no quedan). La guardas antes de validar: así free_map la libera aunque sea mala. Luego le quitas el '\n'.

3. El truco del cuadrado

Para cada casilla apuntas un número: el lado del cuadrado más grande que acaba ahí (esquina de abajo a la derecha).

• Obstáculo → 0.
• Primera fila o primera columna → 1.
• Si no → 1 + el menor de (izquierda, arriba, diagonal).

mapa        números
. . . .     1 1 1 1
. . o .     1 2 0 1
. . . .     1 2 1 1

El número más grande es el 2 en la fila 1, columna 1 → un cuadrado de 2x2 que acaba ahí: filas 0-1, columnas 0-1.

4. Empates: solo >

Recorres de arriba abajo y de izquierda a derecha. Guardas el récord solo si es mayor (>, no >=). Así, si empata, se queda el primero que viste: el de más arriba y más a la izquierda.

bsq función por función

Cuándo es map error

fscanf no lee 4 cosas       falta algún carácter
cabecera sin \n             getline del resto da -1
líneas < 1                  "0 . o x"
dos caracteres iguales      ". . x"
línea vacía o sin \n        len <= 1 o el último no es '\n'
largo distinto              len != cols (cols = ancho de la fila 0)
carácter raro               ni vacío ni obstáculo
faltan líneas               getline da -1
no se puede abrir           fopen da NULL

Checklist

• #define _POSIX_C_SOURCE 200809L antes de los includes (para getline)
• map error con fputs("map error\n", stderr)
• calloc para el array de líneas (todo NULL → free seguro)
• el \n se quita al leer y se vuelve a poner al imprimir
• empate → >, no >=
• free de cada línea y del array (la tabla size va en la pila) · fclose de cada fichero

Otras soluciones

Ninguna mejora a Optim para este subject. Ojo: hay dos subjects de bsq distintos. Mira cuál te toca.