Click here to Skip to main content
16,015,393 members
Please Sign up or sign in to vote.
1.00/5 (3 votes)
See more:
bsq -- finds and prints the biggest square in a map

I
must find the largest possible square on a board while avoiding obstacles. The board is represented by a file passed as the program’s argument, respecting those constraints:

• Its first line contains the number of lines on the board (and only that),
• . (representing an empty place) and "o" (representing an obstacle) are the only two allowed characters for the other lines
• All of the lines will be the same length (except the first one)
• There will always be at least one line
• Each line is terminated by \n.

You program must print the board, with some "." replaced by "x" to represent the largest square you found.


5
.....
.o..o
.....
.o...
o...o


What I have tried:

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<fcntl.h>

char* take_name(int size, char** array){
    char* name = (char*)malloc(sizeof(char)* 18);
    int y = 1;
    name = array[y];
    return name;
}

char* take_content(char* name){
    char* str = (char*)malloc(sizeof(char)*400), *number = (char*)malloc(sizeof(char)*50);
    int fd = open(name,O_RDONLY), shower, in = 0 ;
    char a;
    while((shower = read(fd, &a, 1)) != 0){
        if(a== 'o' || a == '.' || a == '\n')
        str[in++] = a;
    }
    return str;
}

void remark_condition(char* content){
    
}

void main_procedures(char* content, int size_row_line){
    remark_condition(content);

}

void my_bsq(int size, char** array){
    char*name = take_name(size, array);
    char* content = take_content(name);
    printf("%s\n", content);
    int  sized = 5;
    main_procedures(content, sized);
    
}

int* ar(char** arra){
    int num[20], i = 0, ins = 0;
    for(int y = 0; arra[y]; y++){
        for(int k = 0; arra[y][k]; k++){
            if(arra[y][k] == '.'){
                num[y] = 1;
            }
            else if(arra[y][k] == 'o'){
                num[y] = 0;
            }
        }
    }
    return num;
}

int main(int ac, char** array){
    my_bsq(ac, array);
    return 0;
}

I tried but i am facing with a problem when I have to work with integer matrix
Posted
Updated 23-Feb-23 5:53am
Comments
Richard MacCutchan 23-Feb-23 9:22am    
"but i am facing with a problem"
You need to explain exactly what the problem is and where it occurs. Please use the Improve question link above, and add complete details of what is not working.

1 solution

Assume you have the board
....o.
......
....o.
o.....
...o..
......
and suppose your starting position is (row, col) = (1,1).
At (1,1) there is no obstacle, hence you may occupy it and set area = 1:
....o.
.x....
....o.
o.....
...o..
......
Now try to expand your square in the left-down direction. since (1,2), (2,2), (2,1) don't contain obstacles. occupy them
....o.
.xx...
.xx.o.
o.....
...o..
......
and set yor area = 4.
Going on, you may find that (1,3), (2,3), (3,3), (3,2), (3,1) don't contain any obstacle. Occupy them:
....o.
.xxx..
.xxxo.
oxxx..
...o..
......
and set area = 9
Now, trying to continue, you find the first obstacle, at (3,4), so you have to stop and say that max area, for top-left square starting from (1,1) is 9.

Iterating such process starting from all the square of the board (keeping track of the max area found) gives you a brute force approach (that can be easily optimized).
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900