蓝桥杯训练历届试题 剪格子

发表于由
问题描述

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

+–*–+–+
|10* 1|52|
+–****–+
|20|30* 1|
*******–+
| 1| 2| 3|
+–+–+–+

我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。

本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。

如果无法分割，则输出 0。

输入格式

程序先读入两个整数 m n 用空格分割 (m,n<10)。

表示表格的宽度和高度。

接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。

输出格式
输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。
样例输入1
3 3
10 1 52
20 30 1
1 2 3
样例输出1
3
样例输入2
4 3
1 1 1 1
1 30 80 2
1 1 1 100
样例输出2
10
解答：
很明显，题目是一个典型的DFS题目，我们只需要从左上角开始进行有序DFS，每走一步都需要关注是否越界，是否超越所有数目的一半。
其中，我们需要注意的是真正找到的数字能否把图案一分为二，因此我们的DFS必须有顺序性，既先下，后右，再上，再左的顺序来。
另外就是输入的时候是先输入m后输入n，需要注意。
代码：

#include <iostream>

#include <queue>

#include <iomanip>

#include <math.h>

#include <vector>

#include <string>

#include <algorithm>

#include <map>

#include<cstring>

#include<ctype.h>

#include<math.h>

using namespace std;

int dx[4]={0,1,0,-1};

int dy[4]={1,0,-1,0};//每次走一步的增量

bool is_use[20][20];

int vx[20][20];

int M,N,SUM;

bool judge(int x,int y,int num)

{

    if(x<0||y<0||x>N–1||y>M–1)

    {

        return 1;

    }

    if(is_use[x][y])

        return 1;

    if(num+vx[x][y] > SUM)

        return 1;

    return 0;

}

int dfs(int x,int y,int num)

{

    if(num == SUM/2)

    {

        return 1;

    }

    for(int i = 0 ; i < 4;i++)// 依次走4步进行尝试

    {

        int new_x = x + dx[i];

        int new_y = y + dy[i];

        if(judge(new_x, new_y, num))

            continue;

        is_use[new_x][new_y] = true;

        int res = dfs(new_x, new_y, num+vx[new_x][new_y]);

        if(res)

            return res + 1;

        is_use[new_x][new_y] = false;

    }

    return 0;

}

int main(int argc, const char * argv[]) {

    cin>>M;

    cin>>N;

    SUM = 0 ;

    for(int i = 0 ; i < N;i++)

        for(int j = 0 ; j < M;j++)

        {

            cin>>vx[i][j];

            SUM+=vx[i][j];

        }

    if(SUM!=2*(int)SUM/2)

    {

        cout<<0;

        return 0;

    }

    for(int i = 0 ; i < N;i++)

        for(int j = 0 ; j < M;j++)

        {

            is_use[i][j] = false;

        }

    is_use[0][0] = true;

    cout<<dfs(0,0,vx[0][0]);

}

发表评论