[ad_1]
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
.
ボードのすべての正方形から開始してこのようなプロセスを繰り返す (見つかった最大領域を追跡する) と、ブルート フォース アプローチが得られます (これは簡単に最適化できます)。
[ad_2]
コメント