http://lx.lanqiao.cn/problem.page?gpid=T27
歷屆試題 剪格子
時間限制：1.0s 內存限制：256.0MB
提交此題 錦囊1 錦囊2
問題描述
如下圖所示，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

/*
很明顯是搜索題，根據題意可知起點就是左上角那個點，a[0][0].問題多解求最優宜用DFS
*/
AC_code:

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int a[15][15]; bool vis[15][15]; int n,m,sum,minLen; int step_x[] = {-1,1,0,0},step_y[] = {0,0,-1,1};//上下左右四個方向 void DFS(int x,int y,int count,int aim) {vis[x][y] = true;if(aim > sum/2)//可行性剪枝return ;if(aim == sum/2){if(count < minLen)minLen = count;return ;}for(int i = 0; i < 4; i++){int xx = x + step_x[i];int yy = y + step_y[i];if(!vis[xx][yy]&&xx>=0&&xx<n&&yy>=0&&yy<m){DFS(xx,yy,count+1,aim+a[xx][yy]);vis[xx][yy] = false;}} } int main() {cin>>m>>n;for(int i = 0; i < n; i++){for(int j = 0; j< m; j++){cin>>a[i][j];sum += a[i][j];}}if(sum&1)cout<<"0"<<endl;else{minLen = INF;DFS(0,0,1,a[0][0]);if(minLen != INF)cout<<minLen<<endl;elsecout<<"0"<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的蓝桥杯历届试题 剪格子 （DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。