蓝桥杯C/C++省赛：剪格子

叶茂林

发布于 2023-07-30 13:23:27

1350

发布于 2023-07-30 13:23:27

文章被收录于专栏：叶子的开发者社区

题目描述

如图p1.jpg所示，3 x 3 的格子中填写了一些整数。

我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。如果无法分割，则输出 0

程序输入输出格式要求：程序先读入两个整数 m n 用空格分割 (m,n<10) 表示表格的宽度和高度接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000 程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。

例如：用户输入：

3 3 10 1 52 20 30 1 1 2 3

则程序输出：

3

再例如：用户输入：

4 3 1 1 1 1 1 30 80 2 1 1 1 100

则程序输出：

10

资源约定：峰值内存消耗 < 64M CPU消耗 < 5000ms

思路分析

问题是可以变成路径问题，如果有解，那么找出一条从左上角开始的一条路径，这条路径的带权长度为总路径长度的一半。

采用深度优先遍历搜索，递归求解。

递归有两个问题需要解决，一个是什么时候return回去，一个是往哪里递归。

递归结束的条件一般是遇到边界返回，或者是找到解，这里存在最优解的情况，所以还需要记录每次解，将其和当前最优解进行比较。

方向是往上下左右递归，这里需要记得标记为已访问之后，回溯的时候需要取消标记，重新标记为未访问。然后距离和计数都退回上一步的状态。

AC代码

#include<iostream>
using namespace std;
int map[16][16];
int direction[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
bool visited[16][16]={false};
int sum=0;
int answer=0,current=0,count=0;
int m,n;
const int OK=0;
const int ERROR=1;
int DFS(int x,int y){
    if(x<0||y<0||x>=n||y>=m||visited[x][y])
        return ERROR;
    visited[x][y]= true;
    current+=map[x][y];
    count++;
    if(current*2==sum){
        if(answer&&count>=answer)
            return OK;
        answer=count;
        return OK;
    }else if(current*2>sum)
        return OK;
    for(int i=0;i<4;i++){
        if(DFS(x+direction[i][0],y+direction[i][1])==OK){
            visited[x+direction[i][0]][y+direction[i][1]]=false;
            current-=map[x+direction[i][0]][y+direction[i][1]];
            count--;
        }
    }
    return OK;
}
int main(){
    cin>>m>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>map[i][j];
            sum+=map[i][j];
        }
    DFS(0,0);
    cout<<answer;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-09，如有侵权请联系 cloudcommunity@tencent.com 删除

c++