小岛面积,C\C++交流,技术交流,鱼C论坛

巴巴鲁 发表于 2020-8-21 21:35:34

小岛面积

本帖最后由巴巴鲁于 2020-8-21 21:38 编辑

/*
1 代表海岸线，0 代表小岛。求小岛面积（即被 1 中包围的 0 的个数）。
注意：仅求这样的 0，该 0 所在行中被两个 1 包围，该 0 所在列中被两个
*/

#include <stdio.h>
#include <stdlib.h>
#define N 6 // 假设是6维的方阵

void input(int (*arr));
int check(int (*arr), int row, int col);

int main(void)
{
int i, j;
int count = 0;
int arr = {0};

input(arr);

// 由题意知，小岛在矩阵边缘不属于小岛面积
for(i = 1; i < N-1; i++)
{
for(j = 1; j < N-1; j++)
{
// 只判断是小岛周围
if(arr == 0)
{
if(check(arr, i, j)) // 如果检查后满足条件,小岛面积加1
{
count++;
}
}
}
}

printf("小岛面积为%d\n",count);
system("pause");
return 0;
}

void input(int (*arr))
{
int i, j;

for(i = 0; i < N; i++)
{
for(j = 0; j < N; j++)
{
scanf("%d",&arr); // 只能输入0或1
if(arr != 0 && arr != 1)
{
printf("输入错误，退出程序");
exit(1);
}
}
}
}

// 判断是否符合题目要求
int check(int (*arr), int row, int col)
{
int h, l, m, n;
m = n = 0;

// 检查行
for(h = row, l = col; l >= 0; l--)
{
if(arr == 1)
{
for(h = row, l = col; l < N; l++)
{
if(arr == 1)
{
n++; // 都满足，n+1
break;
}
}
if(n == 1)
{
break;
}
}
}

// 检查列
for(h = row, l = col; h >= 0; h--)
{
if(arr == 1)

for(h = row, l = col; h < N; h++)
{
if(arr == 1)
{
m++; // 都满足，m+1
break;
}
}
if(m == 1)
{
break;
}
}

if(m + n == 2) // 两个条件都成立
{
return 1;
}
return 0;
}
样例输入：
1 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 0
1 1 0 1 1 1
0 1 0 1 0 0
1 1 1 1 1 1
样例输出：
8

我输出之后就这样没反应，是我代码的问题吗？哪个大佬们看一下{:10_254:}

Cool_Breeze 发表于 2020-8-21 21:35:35

# 太难了
# 链表忘了，又回去复习了一下
# 代码很糟糕
#include<stdio.h>
#include<malloc.h>

#define N 6

typedef struct ZERO //标记不被包围 0 的位置
{
int count;
int x;
int y;
struct ZERO *next;
} *ZEROP;

int adjacent_to_zero(ZEROP head, ZEROP point); //检查是否与不被包围 0 相邻
void print_struct(ZEROP, char*);
ZEROP pop(ZEROP*, int n, int*);
int main(void)
{
int arr = { 1, 1, 1, 1, 1, 1,
   1, 1, 0, 0, 0, 1,
   1, 0, 0, 0, 1, 0,
   1, 1, 0, 1, 1, 1,
   0, 1, 0, 1, 0, 0,
   1, 1, 1, 1, 1, 1};

int i = 0;
int j = 0;
int count = 0;
char un_zero_str = "被包围 0";
char zero_str = "不被包围 0";
ZEROP head, pn, pend; // head 不被包围 0 的位置头指针
ZEROP un_head, un_pn, un_pend; // un_head 未知不被包围 0 的位置头指针
ZEROP temp = NULL;
for (i=0; i<N; i++) // 查找最外层有没有 0
{
for (j=0; j<N; j++)
{
if (i == 0 || i == N-1 || j == 0 || j == N-1)
{
if (!arr)
{
if (count == 0)
{
head = malloc(sizeof(struct ZERO));
head->x = i;
head->y = j;
head->next = NULL;
pn = pend = head;
count++;
head->count = count;
}
else
{
count++;
pend = malloc(sizeof(struct ZERO));
pn->next = pend;
pend->count = count;
pend->x = i;
pend->y = j;
pend->next = NULL;
pn = pend; //标记 1

}

}
continue;
}
}
}
int find = 2;
if (!count) // 最外层没有 0 里面所有0都是被包围的0
{
find = 0;
}
int mark = 0;
int un_count = 0;
for (i=1; i<N-1; i++)
{
for (j=1; j<N-1; j++)
{
if (arr) continue;
temp = malloc(sizeof(struct ZERO));
temp->x = i;
temp->y = j;
temp->next = NULL;
if (!find) // 最外层没有 0
{
if (count == 0)
{
head = temp;
head->next = NULL;
pn = pend = head;
count++;
head->count = count;
continue;
}
else
{
count++;
pn->next = temp;
temp->count = count;
pn = temp; //标记 1

}
}
else if (adjacent_to_zero(head, temp)) // 最外层有 0
{
un_count++;
if (!mark)
{
un_head = temp;
un_head->count = un_count;
un_pn = un_head;
mark = 1;
continue;

}
un_pn->next = temp;
temp->count = un_count;
un_pn = temp;
}
else
{
count ++;
pn->next = temp; //接着标记 1
temp->count = count;
pn = temp;
}
}
}
if (!find) // 最外层没有 0 直接打印结果
{
print_struct(head, zero_str);
return 0;
}
//print_struct(un_head, un_zero_str);
temp = un_head;
int one = 0;
while (1)
{
one ++;
if (! adjacent_to_zero(head, temp)) //将未知 0 转入不被包围的 0
{
count++;
//转入后更新链表
if (un_head->next)
temp = pop(&un_head, temp->count, &find);
else find = 0;
//print_struct(head, zero_str);
//printf("count = %d\n", count);
temp->count = count;
pn->next = temp; //接着标记 1
pn = temp;
if (!find) break;
if (find == 1)
{
temp = un_head;
continue;
}
}
//printf("one = %d\n", one);
if (!temp->next) break;
temp = temp->next;
}
//free(p);
print_struct(head, zero_str);
if (find)
print_struct(un_head, un_zero_str);
return 0;
}

int adjacent_to_zero(ZEROP head, ZEROP point)
{
while(1)
{
if (head->x == point->x) //同一行
{
if (head->y == point->y-1 || head->y == point->y+1)
return 0;
}
if (head->y == point->y)
{
if (head->x == point->x+1 || head->x == point->x-1) //同一列
return 0;
}
if (head->next == NULL) break;
head = head->next;
}
return 1;
}

void print_struct(ZEROP head, char* title)
{
printf("%s:\n",title);
while (1)
{
printf("COUNT = %d\tX = %d\tY = %d\n",head->count ,head->x+1 ,head->y+1);
if (!head->next) break;
head = head->next;
}
}

ZEROP pop(ZEROP* linked_list, int n, int* find)
{
int count = 0;
ZEROP result, previous;
previous = result = *linked_list;
while (1)
{
if (previous->count == n && count == 0)
{
*linked_list = previous->next;
*find = 1;
return previous;
}
else if (result->count == n)
{
previous->next = result->next;
*find = 1;
return result;
}
if (!result->next) break;
previous = result;
result = result->next;
}
*find = 2;
return result;
}
result:
不被包围 0:
COUNT = 1    X = 3 Y = 6
COUNT = 2    X = 5 Y = 1
COUNT = 3    X = 5 Y = 6
COUNT = 4    X = 5 Y = 5
被包围 0:
COUNT = 1    X = 2 Y = 3
COUNT = 2    X = 2 Y = 4
COUNT = 3    X = 2 Y = 5
COUNT = 4    X = 3 Y = 2
COUNT = 5    X = 3 Y = 3
COUNT = 6    X = 3 Y = 4
COUNT = 7    X = 4 Y = 3
COUNT = 8    X = 5 Y = 3

--------------------------------
Process exited after 0.01647 seconds with return value 0
请按任意键继续. . .

编程白痴· 发表于 2020-8-22 08:40:28

/*
1 代表海岸线，0 代表小岛。求小岛面积（即被 1 中包围的 0 的个数）。
注意：仅求这样的 0，该 0 所在行中被两个 1 包围，该 0 所在列中被两个
*/

#include <stdio.h>
#include <stdlib.h>
#define N 6 // 假设是6维的方阵

void input(int (*arr));
int check(int (*arr), int row, int col);

int main(void)
{
            int i, j;
            int count = 0;
            int arr = {0};

            input(arr);

            // 由题意知，小岛在矩阵边缘不属于小岛面积
            for(i = 0; i < N; i++) //问题 1
            {
                     for(j = 0; j < N; j++)//问题2
                     {
                           // 只判断是小岛周围
                           if(arr == 0)
                           {
                                    if(check(arr, i, j)) // 如果检查后满足条件,小岛面积加1
                                    {
                                             count++;
                                    }
                           }
                     }
            }

            printf("小岛面积为%d\n",count);
            system("pause");
            return 0;
}

void input(int (*arr))
{
            int i, j;

            for(i = 0; i < N; i++)
            {
                     for(j = 0; j < N; j++)
                     {
                           scanf("%d",&arr); // 只能输入0或1
                           if(arr != 0 && arr != 1)
                           {
                                    printf("输入错误，退出程序");
                                    exit(1);
                           }
                     }
            }
}

// 判断是否符合题目要求
int check(int (*arr), int row, int col)
{
            int h, l, m, n;
            m = n = 0;

            // 检查行
            for(h = row, l = col; l >= 0; l--)
            {
                     if(arr == 1)
                     {
                           for(h = row, l = col; l < N; l++)
                           {
                                    if(arr == 1)
                                    {
                                             n++; // 都满足，n+1
                                             break;
                                    }
                           }
                           if(n == 1)
                           {
                                    break;
                           }
                     }
            }

            // 检查列
            for(h = row, l = col; h >= 0; h--)
            {
                     if(arr == 1)

                           for(h = row, l = col; h < N; h++)
                           {
                                    if(arr == 1)
                                    {
                                             m++; // 都满足，m+1
                                             break;
                                    }
                           }
                           if(m == 1)
                           {
                                    break;
                           }
            }

            if(m + n == 2) // 两个条件都成立
            {
                     return 1;
            }
            return 0;
}

编程白痴· 发表于 2020-8-22 08:41:58

大佬，你这是作业？我最近刚看c语言，还写不出这种程序{:10_266:}

巴巴鲁 发表于 2020-8-22 09:16:01

编程白痴· 发表于 2020-8-22 08:40
/*
1 代表海岸线，0 代表小岛。求小岛面积（即被 1 中包围的 0 的个数）。
注意：仅求这样的 0，该 0...

没得反应啊，而且我感觉矩阵的最外面不需要判断，因为肯定不符合题意

巴巴鲁 发表于 2020-8-22 09:16:31

编程白痴· 发表于 2020-8-22 08:41
大佬，你这是作业？我最近刚看c语言，还写不出这种程序

没事找的题

风过无痕1989 发表于 2020-8-22 11:50:04

我觉得边界上的 0 应该算，如：arr 和 arr，不在边界上的0不算，如：arr

巴巴鲁 发表于 2020-8-22 12:34:17

风过无痕1989 发表于 2020-8-22 11:50
我觉得边界上的 0 应该算，如：arr 和 arr，不在边界上的0不算，如：arr

但是小岛在边上的话，最多只能被3个海岸线包围啊，和题目上的不一样

有理由相信 发表于 2020-8-23 07:56:37

111111
110000
100011
100000
111111
遇到这种情况怎么算？

巴巴鲁 发表于 2020-8-23 08:57:34

有理由相信发表于 2020-8-23 07:56
111111
110000
100011

加粗的三个呗
111111
110000
100011
100000
111111

有理由相信 发表于 2020-8-23 09:22:42

巴巴鲁发表于 2020-8-23 08:57
加粗的三个呗
111111
110000

懂了

风过无痕1989 发表于 2020-8-23 10:01:29

巴巴鲁发表于 2020-8-23 08:57
加粗的三个呗
111111
110000

加粗的三个，也没有被完全封闭，它们上面与下面都是0，所以，还得考虑边界上的0才行

巴巴鲁 发表于 2020-8-23 10:10:34

风过无痕1989 发表于 2020-8-23 10:01
加粗的三个，也没有被完全封闭，它们上面与下面都是0，所以，还得考虑边界上的0才行

我理解的是只要0所在行左右，所在列上下有1就行了
你看看那个输出输入样例

巴巴鲁 发表于 2020-8-23 19:37:32

Cool_Breeze 发表于 2020-8-23 15:31
# 太难了
# 链表忘了，又回去复习了一下
# 代码很糟糕

强，让我好好研究研究{:10_256:}

页: [1]

鱼C论坛's Archiver

小岛面积