剪格子

如圖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

(參見p2.jpg)

資源約定：
峰值內存消耗 < 64M
CPU消耗 < 5000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內容。

所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。

注意: main函數需要返回0
注意: 只使用ANSI C/ANSI C++ 標準，不要調用依賴于編譯環境或操作系統的特殊函數。
注意: 所有依賴的函數必須明確地在源文件中 #include ， 不能通過工程設置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

代碼

#include <iostream> #include <algorithm>using namespace std;int m, n; int total; int g[10][10]; int vis[10][10]; int ans = 100;void f(int i, int j, int sum, int cnt) {if (sum > total / 2) return;if (sum == total / 2) {ans = min(ans, cnt);return;}vis[i][j]=1; // 可以有四個分支往下走if (i + 1 <= n-1&&vis[i+1][j]==0)f(i + 1, j, sum + g[i][j], cnt + 1);if (i - 1 >= 0&&vis[i-1][j]==0)f(i - 1, j, sum + g[i][j], cnt + 1);if (j + 1 <= m-1&&vis[i][j+1]==0)f(i, j + 1, sum + g[i][j], cnt + 1);if (j - 1 >= 0&&vis[i][j-1]==0)f(i, j - 1, sum + g[i][j], cnt + 1);vis[i][j]=0; }int main(int argc, const char *argv[]) {scanf("%d %d", &m, &n);for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {scanf("%d", &g[i][j]);total += g[i][j];}}f(0, 0, 0, 0);if(ans!=100)printf("%d\n",ans);elseprintf("%d\n",0);return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的征战蓝桥 —— 2013年第四届 —— C/C++A组第9题——剪格子的全部內容，希望文章能夠幫你解決所遇到的問題。

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