0%

蓝桥杯PREV04-剪格子

发表于

题目链接

题目概述

选出格子中的一个连续区域，使该区域数字之和为所有数之和的一半，并且要求该连续区域中元素数量最少。

题目分析

dfs，搜索过程中记录目前搜索过的格子数量以及和。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;

int map[15][15], vst[15][15], _sum, _ans=1002, n, m;

int check(int x, int y){
    if(x<0||x>=m||y<0||y>=n)
        return 0;
    return !vst[y][x];
}

void dfs(int x, int y, int sum, int step){
    if(!check(x, y))
        return;
    step++;
    sum+=map[y][x];
    if(sum==_sum/2){
        _ans=min(_ans, step);
        return;
    }
    if(sum>_sum/2)
        return;

    vst[y][x]=1;
    dfs(x+1, y, sum, step);dfs(x, y+1, sum, step);
    dfs(x-1, y, sum, step);dfs(x, y-1, sum, step);
    vst[y][x]=0;
}

int main(){
    cin>>m>>n;
    for(int j=0; j<n; j++){
        for(int i=0; i<m; i++){
            cin>>map[j][i];
            _sum+=map[j][i];
        }
    }
    dfs(0,0,0,0);
    if(_ans>m*n)
        cout<<0<<endl;
    else
        cout<<_ans<<endl;
    return 0;
}

自我总结

本来想用bfs的，但似乎写起来比dfs麻烦，看来还是应该优先考虑dfs。