在一个二维数组/矩阵找到平方了1的中 [英] Finding square made of 1's in a 2D array/matrix
问题描述
感谢您的帮助。我真的AP preciate它。我一直在寻找解决方案的SO，但没有什么是正是我需要的。我需要在C
我的任务是找到最大的广场1的阵列。该阵列由只有0和1，并期待，例如，像这样的：
4 4
0 1 1 1
0 1 0 1
0 1 1 1
1 0 1 0
输出应打印 [行] [COL] 的左上角1和 [行] [COL] 的右下角的，因此，它应该是，我的例子中， [0] [1] 和 [2] [3 ] 。
我用我的 GETCOLOR（）函数来获得 [行] [COL] 点值。
另外，我有这些功能获得最长的水平和垂直线条。由于某种原因，它们只与具有相同数目的行和列的数组。当我使用，例如，4议和5行的阵列，它不工作的权利。 AAN你帮帮我好吗？
无效getHline（位图* ARR）
{
INT I，J，K;
INT线，LINE_START，LINE_END，LINE_MAX = 0; //水平
对于（K = 0; K＆LT; arr-＆GT;行; k ++）
{
对于（i = 0; I＆LT; arr-＆GT;的行;我++）
{
如果（！GETCOLOR（ARR，K，I））
{
继续;
} 为（J = I; J＆LT; arr-＆GT; COLS; J ++）
{
如果（！GETCOLOR（ARR，K，J））
{
打破;
}
} j--; 如果（J - 1 + 1＆GT; LINE_MAX）
{
行= K;
LINE_START = I;
LINE_END = j的;
LINE_MAX = LINE_END-LINE_START + 1;
}
}
} 的printf（横向\\ n）;
的printf（启动：[％D]。[％D]。\\ n，LINE_START，线）;
的printf（结束：[％D]。[％D]。\\ n，LINE_END，线）;
}无效getVline（位图* ARR）
{
INT I，J，K;
INT关口，col_start，col_end，col_max = 0; 对于（K = 0; K＆LT; arr-＆GT; COLS; k ++）
{
对于（i = 0; I＆LT; arr-＆GT;的行;我++）
{
如果继续（GETCOLOR（ARR，I，K）！）; 为（J = I; J＆LT; arr-＆GT; COLS; J ++）
{
如果中断（GETCOLOR（ARR，J，K）！）;
} j--; 如果（J - 1 + 1＆GT; col_max）
{
COL = K;
col_start = I;
col_end = j的;
col_max = col_end-col_start + 1;
}
}
} 的printf（\\ nverticaly \\ n）;
的printf（启动：[％D]。[％D]。\\ n，山坳，col_start）;
的printf（结束：[％D]。[％D]。\\ n，山坳，col_end）;
}
如果你试图让这个已经注意到最长的水平线和垂直线做了最大的广场。因为它们可以分离并没有与之相关的平方。
在试图解决一个复杂的问题，不要试图去解决它的一次。
我们有第一想到的是，阵列的每个点用正方形（最大为每个点）相关联。因此，我们必须找到方：我们把数组的一个点，则我们通过步骤，通过连续的水平和垂直线移动。对于每一步，我们检查，如果我们得到一个正方形，并重复这个过程，直到我们得到与单点相关的最大的广场。
每一次我们得到了点相关联的最大的广场，我们检查它是否是最大的比一些previous点相关联的最后一个最大的广场。
连接这些部件之后，我们得到我们的最终方案。
在程序中使用的变量的说明：
链接程序 http://pastebin.com/Yw05Gbtg 或查看在这里：
编辑：
的#include＆LT;＆stdio.h中GT;主要（）
{
INT线= 4，COLS = 4;
INT ARR [4] [4] = {
{0,1,1,1，}，
{0,1,0,1，}，
{0,1,1,1，}，
{1,0,1,0，}
};
INT x_start，y_start，x_end，y_end，D_MAX = 0;
INT I，J，K，L;
INT col_start，LINE_START，col_end，LINE_END，检查; 为（y_start = 0; y_start＆下;线; y_start ++）{
为（x_start = 0; x_start＆下; COLS; x_start ++）{
x_end = x_start;
y_end = y_start;
对于（i = x_start，J = y_start; I＆LT;＆COLS功放;＆放大器; J＆LT;线;我++，J ++）{//水平和垂直方向移动
如果（！改编[y_start] [I] ||！改编[j]的[x_start]）{//检查是否在水平或垂直线是不连续的
打破;
}
其他{
检查= 1;
对于（K = x_start，L = y_start; K＆LT;我+ 1安培;＆安培; L＆LT; J + 1; K- ++，L ++）{//检查方
如果（！常用3 [j]的[K] ||！改编[L] [I]）{
检查= 0;
打破;
}
}
如果（检查）{//如果方则
x_end = I;
y_end = j的;
}
}
}
如果（时（x_end-x_start）GT; D_MAX）{
col_start = x_start;
LINE_START = y_start;
col_end = x_end;
LINE_END = y_end;
D_MAX = col_end，col_start;
}
}
} 的printf（最大的广场为：\\ n [％D]。[％d个]×[％D]。[％D]。\\ n，LINE_START，col_start，LINE_END，col_end）; //这只是检查程序是否正常运行
为（y_start = LINE_START; y_start＆下; LINE_END + 1; y_start ++）{
的printf（\\ n）;
为（x_start = col_start; x_start＆下; col_end + 1; x_start ++）{
的printf（％d个，编曲[y_start] [x_start]）;
}
}
的printf（\\ n）;
}
Thanks for helping. I really appreciate it. I Have been searching for solution on SO, but nothing is exactly what I need. I need it in C.
My task is to find "largest square" of 1's in an array. The array consists of only 0's and 1's and looks, for example, like this:
4 4
0 1 1 1
0 1 0 1
0 1 1 1
1 0 1 0
Output should print [row][col] of "upper left corner" 1, and [row][col] of "lower right corner", So it should be, for my example, [0][1] and [2][3].
I am using my getcolor() function to get value on [row][col] spot.
Also, I have these functions to get longest horizontal and vertical lines. For some reason they only work with arrays with the same number of columns and rows. When I use, for example, an array with 4 cols and 5 rows, it does not work right. Aan you help me please?
void getHline(Bitmap *arr)
{
int i, j, k;
int line, line_start, line_end, line_max = 0;
// Horizontally
for (k = 0; k < arr->rows; k++)
{
for (i = 0; i < arr->rows; i++)
{
if(!getcolor(arr, k, i))
{
continue;
}
for(j = i; j < arr->cols; j++)
{
if(!getcolor(arr, k, j))
{
break;
}
}
j--;
if(j - i + 1 > line_max)
{
line = k;
line_start = i;
line_end = j;
line_max = line_end-line_start+1;
}
}
}
printf("horizontally\n");
printf("start: [%d][%d]\n", line_start, line);
printf("end: [%d][%d]\n", line_end, line);
}
void getVline(Bitmap *arr)
{
int i, j, k;
int col, col_start, col_end, col_max = 0;
for(k = 0; k < arr->cols; k++)
{
for (i = 0; i < arr->rows; i++)
{
if (!getcolor(arr,i,k)) continue;
for (j = i; j <arr->cols; j++)
{
if (!getcolor(arr,j,k)) break;
}
j--;
if (j - i + 1 >col_max)
{
col = k;
col_start = i;
col_end = j;
col_max = col_end-col_start+1;
}
}
}
printf("\nverticaly\n");
printf("start: [%d][%d]\n", col, col_start);
printf("end: [%d][%d]\n", col, col_end);
}
If you're trying to get the largest square this has noting to do with the longest horizontal and vertical lines. Because they could be separated and no square associated with them.
When trying to solve a complex problem, don't try to solve it all at once.
The first think we have is that each point of the array is associated with a square (the largest one for each point). So we have to find that square: We take a point of the array then we move by steps through a continuous horizontal and vertical lines. For each step we check if we get a square and repeat the process until we get the largest square associated with that single point.
Each time we get the largest square associated with a point we check if it's largest than the last largest square associated with some previous point.
After connecting these parts we get our final program.
Explanation of the variables used in the program:
Link to the program http://pastebin.com/Yw05Gbtg or view it here:
EDIT:
#include <stdio.h>
main()
{
int lines=4, cols=4;
int arr[4][4] = {
{0,1,1,1,},
{0,1,0,1,},
{0,1,1,1,},
{1,0,1,0,}
};
int x_start, y_start, x_end, y_end, d_max=0;
int i, j, k, l;
int col_start, line_start, col_end, line_end, checker;
for (y_start=0; y_start<lines; y_start++){
for (x_start=0; x_start<cols; x_start++){
x_end = x_start;
y_end = y_start;
for (i=x_start, j=y_start; i<cols && j<lines; i++, j++){ // moving horizontally and vertically
if (!arr[y_start][i] || !arr[j][x_start]){ // checking if the horizontal or vertical lines are not continuous
break;
}
else {
checker = 1;
for (k=x_start, l=y_start; k<i+1 && l<j+1; k++, l++){ // check if square
if (!arr[j][k] || !arr[l][i]){
checker = 0;
break;
}
}
if (checker){ // if square then
x_end = i;
y_end = j;
}
}
}
if ((x_end-x_start)>d_max){
col_start = x_start;
line_start = y_start;
col_end = x_end;
line_end = y_end;
d_max = col_end-col_start;
}
}
}
printf("The largest square is:\n[%d][%d] x [%d][%d]\n", line_start, col_start, line_end, col_end);
// this is only to check if the program is working properly
for (y_start=line_start; y_start<line_end+1; y_start++){
printf("\n ");
for (x_start=col_start; x_start<col_end+1; x_start++){
printf("%d ", arr[y_start][x_start]);
}
}
printf("\n");
}
这篇关于在一个二维数组/矩阵找到平方了1的中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
