【解決方法】CでBSQのコードを作成して、マップ内の最大の正方形を見つけるにはどうすればよいですか


bsq -- finds and prints the biggest square in a map

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

私が試したこと:

#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;
}

試してみましたが、整数行列を操作する必要があるときに問題に直面しています

解決策 1

ボードがあると仮定します

....o.
......
....o.
o.....
...o..
......

開始位置が (row, col) = (1,1) であるとします。
(1,1) には障害物がないため、占有して面積 = 1 を設定できます。

....o.
.x....
....o.
o.....
...o..
......

次に、正方形を左下方向に拡大してみてください。 (1,2)、(2,2)、(2,1) には障害物が含まれていないためです。 それらを占有

....o.
.xx...
.xx.o.
o.....
...o..
......

yor area = 4 に設定します。
続けて、(1,3)、(2,3)、(3,3)、(3,2)、(3,1) に何の障害も含まれていないことがわかるかもしれません。 それらを占有します:

....o.
.xxx..
.xxxo.
oxxx..
...o..
......

とセットエリア= 9
さて、続行しようとすると、(3,4) に最初の障害物が見つかります。そこで停止して、(1,1) から始まる左上の正方形の最大面積を言わなければなりません。 9.

ボードのすべての正方形から開始してこのようなプロセスを繰り返す (見つかった最大領域を追跡する) と、ブルート フォース アプローチが得られます (これは簡単に最適化できます)。

コメント

タイトルとURLをコピーしました