[蓝桥省题](C2013_10) 剪格子

10、剪格子,如下图所示,3*3的格子中填写了一些整数

img样例1

img

我们沿着图中的红色线剪开,得到两个部分,每个部分的数字都是60

本题的要求就是请你编程判定,对给定的m*n的格子中的整数,是否可以分割称两个部分,使得这两个区域的数字和相等,如果存在多种解答,请输出包含左上角格子的那个区域包含的格子的最小数目,如果无法分割,则输出0

程序输入输出格式要求:

  • 程序先读入两个整数m n 用空格分隔(m,n<10)
  • 表示表格的宽度和高度
  • 接下来是n行,每行m个正整数,用空格分开,每个整数不大于10000

程序输出,在所有解中,包含左上角的分割区可能包含的最小格子数目

例如:

3 3
10 1 52
20 30 1
1 2 3

输出:3

题意:意思就是,从左上角,坐标(0,0)出发,去探寻最少能达到矩阵元素总和一半的路径,并且输出它的格子数即可

思路:从最小来看,我们就可以明确是从上往下迭代,而每一种格子又有四个方向的走法,我们很容易就能想到DFS

递归树状图如下所示

img

我们需要明确递归参数,从上图分析可得知,变化的是:x坐标,y坐标,格子值之和,计数

  • 从题意我们可以划定剪枝条件,如下所示:
  • 路径结点值和大于med则退出
  • 坐标越界则不进行递归
  • 若之前路径中有则不递归

则在每次访问的时候,我们都需要一个记录是否已访问的状态数组,这种方法在之前的洪水算法(BFS)和LeetCode51题的N皇后中相近,这是搜索的一堆“哨兵“,能让程序进行回溯,而不是卡死在一个点上重复的走。

每个格子都有四个方向可以走,则我们可根据上述分析写出代码如下所示:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int m, n;//矩阵行、列
int total = 0;//总和
int g[10][10];//矩阵
int ans = 100;//最大格子数
int vis[10][10];//是否访问;
void f(int i, int j, int sum, int cnt)
{
    if (sum > total / 2) return;//大于则返回,代表路径不同
    if(sum==total/2){
        ans = ans < cnt ? ans : cnt;//等于则更新格子最小值,返回寻找是否有更优解
        return;
    }
    vis[i][j] = 1;//记录当前格子访问

    //四个方向
    if (i + 1 < m && !vis[i + 1][j])f(i + 1, j, sum + g[i][j], cnt + 1);
    if (i - 1 >= 0 && !vis[i - 1][j])f(i - 1, j, sum + g[i][j], cnt + 1);
    if (j + 1 < n && !vis[i][j + 1])f(i, j + 1, sum + g[i][j], cnt + 1);
    if (j - 1 >= 0 && !vis[i][j - 1])f(i, j - 1, sum + g[i][j], cnt + 1);
    vis[i][j] = 0;//回溯
}
int main()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++) {
            scanf("%d", &g[i][j]);
            total += g[i][j];
        }
    }
    memset(vis, 0, sizeof(int) * 100);
    printf("%d", total);
    system("pause");
    f(0, 0, 0, 0);
    printf("%d", ans);
    return 0;
}

暴力解法

特殊情况:

2 2
1 1
1 3

dfs只能单向搜索,但是其搜索路径上提前剪枝,并无法达到正确的分支

根据大佬的题解视频就能很轻松的搞定代码,采用的数据结构逻辑思维图如下所示:

img

可以这样理解,从左上角(0,0)这个坐标开始,去判断当前格子值和是否为总值和的一半,如(0,0)就是一个格子的值。

若不为一半,则尝试着添加上一种解法的邻居,每个格子也就是每个坐标都有四个方向有邻居可以添加,同时需要注意剪枝条件,若不满足添加条件则剪枝

添加条件与上述相同:

  • 正在迭代的解法中不能有重复的格子(每次添加新的格子都需要扫描其之前的格子是否存在重复)
  • 格子坐标不能越界
  • 格子值和需要小于总值和一半(若等于,则直接退出)

我们从第一种解法开始迭代,例如:

arr[1]=(0,0)
arr[2]=【(0,0)(1,0)】【(0,0)(0,1)】
arr[3]=【(0,0)(1,0)(0,1)】【(0,0)(1,0)(1,1)】........

代码如下所示:

#define _CRT_SECURE_NO_WARNINGS
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define ArrMaxSize 100
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int Status;
typedef int Bool;
typedef struct CoordNode
{
    int x;
    int y;
    struct CoordNode* next;
}CoordNode, * CoordLink;
typedef struct DataNode
{
    CoordLink Coor;
    int val;
    struct DataNode* next;
}DataNode, * DataLink;
DataLink arr[100];
int Maze[100][100];


Status InitStructArr()
{
    for (int i = 0; i < ArrMaxSize; i++)
    {
       *(arr + i) = (DataLink)malloc(sizeof(DataNode));
       arr[i]->next = NULL;
       arr[i]->Coor = (CoordLink)malloc(sizeof(CoordNode));
       arr[i]->Coor->next = NULL;
    }
    return OK;
}
Status CopyNode(DataLink *CurNode, DataLink PreNode)
{
    CoordLink p = (*CurNode)->Coor;
    CoordLink s = PreNode->Coor->next;
    while (s)
    {
        p->next = (CoordLink)malloc(sizeof(CoordNode));
        p = p->next;
        p->next = NULL;

        p->x = s->x;
        p->y = s->y;
        s = s->next;
    }

    (*CurNode)->val = PreNode->val;
}
Bool check(DataLink temp, int x, int y)
{
      CoordLink s = temp->Coor->next;
      while (s)
      {
          if (s->x == x && s->y == y)
             return TRUE;
          s = s->next;
      }
          
      return FALSE;
}
int main()
{

    InitStructArr();
    int m, n;
    int total = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            scanf("%d", &Maze[i][j]);
            total += Maze[i][j];
        }
    int med = total / 2;
    printf("med=%d\n", med);
    

    /*约定如下:
    1、采用链表数组来存所有可能的解法,链表数组的容量暂定为100
    2、每一种格子组合均有多种解法,采用链表数组中的下标标记格子数
         1、第一个格子只有0,0一种剪切方法,所以为初始条件
    3、剪切方案采用链表链连接在所属下标中
         1、带头结点,统一情况
         2、剪切方法成员有一个总值,为所有格子之和
         3、剪切方法的坐标组合采用链表形式连接。
    4、采用思路如下:
         1、从上往下迭代,每一次都有四个方向形成四种可能
         2、在坐标迭代的过程中会有重复出现,如有两个格子的(0,0)(0,1)迭代到有三个格子的组合中,会出现第一个坐标向上走的情况
         需要注意去重检测
    5、边界为n行,m列的矩阵,由用户自行输入
    */




    
    /*初始化*/
    arr[1]->next = (DataLink)malloc(sizeof(DataNode));
    arr[1]->next->next = NULL;
    arr[1]->next->Coor = (CoordLink)malloc(sizeof(CoordNode));
    CoordLink p = arr[1]->next->Coor;
    p->next = (CoordLink)malloc(sizeof(CoordNode));
    p = p->next;
    p->next = NULL;
    p->x = 0;
    p->y = 0;
    arr[1]->next->val = Maze[0][0];


    /*从有两种解法的格子开始添加*/
    for (int i = 2; i <= m * n; i++)
    {
        DataLink CurNode = arr[i];//当前解法集合
        DataLink PreNode = arr[i - 1]->next;//上一解法集合
        while (PreNode)//迭代上一解法所有单元
        {
            CoordLink PreList = PreNode->Coor->next;//迭代上一解法单元中所有坐标组合
            while (PreList)
            {
                if ((PreList->x + 1) < n && ((PreNode->val + Maze[PreList->x + 1][PreList->y]) <= med))//向左
                {
                    if (!check(PreNode, PreList->x + 1, PreList->y))//检查此坐标是否已在上一单元的坐标组合中出现
                    {
                        CurNode->next = (DataLink)malloc(sizeof(DataNode));//未出现则创建新的单元
                        CurNode = CurNode->next;//指针指向先的单元(所有解法在尝试中都会统一情况连接,所以CurNode每次都指向解法尾端)
                        CurNode->next = NULL;//后继赋空
                        CurNode->Coor = (CoordLink)malloc(sizeof(CoordNode));//创建新的坐标组合头结点
                        CurNode->Coor->next = NULL;
                        
                        CopyNode(&CurNode, PreNode);//将上一单元的坐标组合深度拷贝到新的单元内
                        CoordLink s1 = CurNode->Coor->next;//寻找坐标组合尾结点
                        while (s1->next) s1 = s1->next;
                        
                        //添加新的坐标形成一个新的单元
                        s1->next = (CoordLink)malloc(sizeof(CoordNode));
                        s1 = s1->next;
                        s1->next = NULL;
                        s1->x = PreList->x + 1;
                        s1->y = PreList->y;
                        CurNode->val += Maze[(s1->x)][(s1->y)];
                    }

                    //判断新的单元是否满足剪切条件
                    if (CurNode->val == med)
                    {
                        printf("%d,%d", CurNode->val, i);
                        system("pause");
                        return 0;
                    }
                }

                //以下类同,探寻新的组合点
                if ((PreList->x - 1 >= 0) && ((PreNode->val + Maze[PreList->x - 1][PreList->y]) <= med))
                {
                    if (!check(PreNode, PreList->x - 1, PreList->y))
                    {
                        CurNode->next = (DataLink)malloc(sizeof(DataNode));
                        CurNode = CurNode->next;
                        CurNode->next = NULL;
                        CurNode->Coor = (CoordLink)malloc(sizeof(CoordNode));
                        CurNode->Coor->next = NULL;
                        CopyNode(&CurNode, PreNode);
                        CoordLink s1 = CurNode->Coor->next;
                        while (s1->next) s1 = s1->next;
                        s1->next = (CoordLink)malloc(sizeof(CoordNode));
                        s1 = s1->next;
                        s1->next = NULL;
                        s1->x = PreList->x - 1;
                        s1->y = PreList->y;
                        CurNode->val += Maze[(s1->x)][(s1->y)];
                    }
                    if (CurNode->val == med)
                    {
                        printf("%d,%d", CurNode->val, i);
                        system("pause");
                        return 0;
                    }
                }

                if ((PreList->y + 1 < m) && ((PreNode->val + Maze[PreList->x][PreList->y + 1]) <= med))
                {
                    if (!check(PreNode, PreList->x, PreList->y + 1))
                    {
                        CurNode->next = (DataLink)malloc(sizeof(DataNode));
                        CurNode = CurNode->next;
                        CurNode->next = NULL;
                        CurNode->Coor = (CoordLink)malloc(sizeof(CoordNode));
                        CurNode->Coor->next = NULL;
                        CopyNode(&CurNode, PreNode);
                        CoordLink s1 = CurNode->Coor->next;
                        while (s1->next) s1 = s1->next;
                        s1->next = (CoordLink)malloc(sizeof(CoordNode));
                        s1 = s1->next;
                        s1->next = NULL;
                        s1->x = PreList->x;
                        s1->y = PreList->y + 1;
                        CurNode->val += Maze[(s1->x)][(s1->y)];
                    }
                    if (CurNode->val == med)
                    {
                        printf("%d,%d", CurNode->val, i);
                        system("pause");
                        return 0;
                    }
                }


                if ((PreList->y - 1 >= 0) && ((PreNode->val + Maze[PreList->x][PreList->y - 1]) <= med))
                {
                    if (!check(PreNode, PreList->x, PreList->y - 1))
                    {
                        CurNode->next = (DataLink)malloc(sizeof(DataNode));
                        CurNode = CurNode->next;
                        CurNode->next = NULL;
                        CurNode->Coor = (CoordLink)malloc(sizeof(CoordNode));
                        CurNode->Coor->next = NULL;
                        CopyNode(&CurNode, PreNode);
                        CoordLink s1 = CurNode->Coor->next;
                        while (s1->next) s1 = s1->next;
                        s1->next = (CoordLink)malloc(sizeof(CoordNode));
                        s1 = s1->next;
                        s1->next = NULL;
                        s1->x = PreList->x;
                        s1->y = PreList->y - 1;
                        CurNode->val += Maze[(s1->x)][(s1->y)];
                    }
                    if (CurNode->val == med)
                    {
                        printf("%d,%d", CurNode->val, i);
                        system("pause");
                        return 0;
                    }
                }
                PreList = PreList->next;
            }
            PreNode = PreNode->next;
        }


        /*检查遍历*/
        DataLink p1 = arr[i]->next;
        printf("第%d种解法:\n", i);
        while (p1)
        {
            CoordLink p2 = p1->Coor->next;
            while (p2)
            {
                printf("(%d,%d) ", p2->x, p2->y);
                p2 = p2->next;
            }
            printf("%d\n", p1->val);
            p1 = p1->next;
        }
        system("pause");
    }
    return 0;
}

教学视频(一)

教学视频(二)

教学视频(三)

本文链接:

https://nullcode.fun/98.html
1 + 6 =
快来做第一个评论的人吧~