// 參考資料: http://blog.csdn.net/xushao_movens/article/details/50637251
#include <iostream>

using namespace std;

#define MAXN 15
#define NO_ANSWER 0xffff

int m, n;
int grid[MAXN][MAXN];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int used[MAXN][MAXN];
int ans;

// 求另一區域的和
// 參數cnt用於返回另一區域的格子數
int rest_sum(int *cnt)
{
    int sum = 0;
    int i, j;
    *cnt = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            if (!used[i][j])
            {
                (*cnt)++;
                sum += grid[i][j];
            }
        }
    }
    return sum;
}

//搜索到(x, y)時左上角區域和sum
void dfs(int x, int y, int sum)
{
    used[x][y] = true;

    int cnt, temp;
    int restSum = rest_sum(&cnt);
    if (sum == restSum)
    {
        temp = n * m - cnt; // 總格子數減去另一區域的格子數, 得到本區域格子數
        if (ans > temp)
            ans = temp; // 求最小答案
        return;
    }

    int i;
    for (i = 0; i < 4; i++) // 四個方向
    {
        // 新坐標
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        // 坐標有效且未被使用
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !used[nx][ny])
        {
            used[nx][ny] = true; // 標記使用
            dfs(nx, ny, sum + grid[nx][ny]); // 尋找子空間的更多解
            used[nx][ny] = false; // 回溯, 恢復原來狀態
        }
    }
}

int main(void)
{
    // 輸入數據
    int i, j;
    cin >> m >> n;
    memset(used, 0, sizeof(used));
    ans = NO_ANSWER;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
            cin >> grid[i][j];
    }

    // 搜索
    dfs(0, 0, grid[0][0]);

    // 輸出結果
    if (ans == NO_ANSWER) // 無答案
        cout << 0 << endl;
    else
        cout << ans << endl;
    return 0;
}

正確  100  15ms  2.5MB  

今天就考了一個與此題非常類似的題：剪郵票

【代碼2：使用變量x、y】
#include <iostream>

using namespace std;

#define MAXN 15
#define NO_ANSWER 0xffff

int m, n;
int grid[MAXN][MAXN];
int dir[][2] = {-1, 0, 1, 0, 0, 1, 0, -1};
bool used[MAXN][MAXN];
int ans = NO_ANSWER;

// 求另一區域(used=0)的和
// 參數cnt用於返回另一區域的格子數
int rest_sum(int *cnt)
{
    int sum = 0;
    int x, y;
    *cnt = 0;
    for (y = 0; y < n; y++)
    {
        for (x = 0; x < m; x++)
        {
            if (!used[y][x])
            {
                (*cnt)++;
                sum += grid[y][x];
            }
        }
    }
    return sum;
}

// 搜索到(x, y)時左上角區域的和sum
void search(int x, int y, int sum)
{
    used[y][x]  = true;

    int grid_num[2];
    int sum2 = rest_sum(&grid_num[1]);
    if (sum == sum2)
    {
        grid_num[0] = m * n - grid_num[1]; // 總格子數減去另一區域的格子數, 得到本區域格子數
        if (ans > grid_num[0]) // ans一開始是一個非常大的數
            ans = grid_num[0]; // 求最小答案
        return;
    }

    int i;
    for (i = 0; i < 4; i++) // 4個方向
    {
        // 新坐標
        int x_new = x + dir[i][0];
        int y_new = y + dir[i][1];

        // 坐標有效且未被使用
        if (x_new >= 0 && x_new < m && y_new >= 0 && y_new < n && !used[y_new][x_new])
        {
            used[y_new][x_new] = true; // 標記使用
            search(x_new, y_new, sum + grid[y_new][x_new]);
            used[y_new][x_new] = false; // 回溯, 恢復原來狀態
        }
    }
}

int main(void)
{
    int x, y;
    memset(used, 0, sizeof(used));
    cin >> m >> n;
    for (y = 0; y < n; y++)
    {
        for (x = 0; x < m; x++)
            cin >> grid[y][x];
    }

    search(0, 0, grid[0][0]);

    if (ans == NO_ANSWER)
        cout << 0 << endl;
    else
        cout << ans << endl;

    return 0;
}

【PHP代碼：生成直觀網頁】
<?php
define('NO_ANSWER', 0xffff); // 這個常量不要改動
define('TABLE_FLOAT', true); // 決定顯示方式

function draw_table($sum1, $sum2, $margin = 0, $correct = false) {
    global $m, $n, $grid, $used;
    if ($correct) {
        $cls = 'correct';
    } else {
        $cls = 'used';
    }
    if (TABLE_FLOAT) {
        $style = ' style="float:left"';
    } else {
        $style = " style=\"margin-left:{$margin}px\"";
    }
    echo "<table border=\"1\" $style>\n";
    for ($y = 0; $y < $n; $y++) {
        echo "\t<tr>\n";
        for ($x = 0; $x < $m; $x++) {
            if ($used[$y][$x]) {
                printf("\t\t<td class=\"%s\">%d</td>\n", $cls, $grid[$y][$x]);
            } else {
                printf("\t\t<td>%d</td>\n", $grid[$y][$x]);
            }
        }
        echo "\t</tr>\n";
    }
    echo "\t<tr>\n\t\t<td class=\"$cls\" colspan=\"$m\">sum1=$sum1</td>\n\t</tr>\n";
    echo "\t<tr>\n\t\t<td colspan=\"$m\">sum2=$sum2</td>\n\t</tr>\n";
    echo "</table>\n";
}

function calc_rest_sum(&$cnt) {
    global $m, $n, $used, $grid;
    $sum = 0;
    $cnt = 0;
    for ($y = 0; $y < $n; $y++) {
        for ($x = 0; $x < $m; $x++) {
            if (!$used[$y][$x]) {
                $cnt++;
                $sum += $grid[$y][$x];
            }
        }
    }
    return $sum;
}

function search($x, $y, $sum, $margin = 0) {
    global $m, $n, $used, $grid, $ans;
    $dir = array(array(-1, 0), array(1, 0), array(0, 1), array(0, -1));
    $used[$y][$x] = true;
    $grid_num = array();
    $sum2 = calc_rest_sum($grid_num[1]);
    if ($sum == $sum2) {
        $grid_num[0] = $m * $n - $grid_num[1];
        if ($ans > $grid_num[0]) {
            $ans = $grid_num[0];
        }
        draw_table($sum, $sum2, $margin, true);
        return;
    } else {
        draw_table($sum, $sum2, $margin);
    }
   
    for ($i = 0; $i < 4; $i++) {
        $x_new = $x + $dir[$i][0];
        $y_new = $y + $dir[$i][1];
        if ($x_new >= 0 && $x_new < $m && $y_new >= 0 && $y_new < $n && !$used[$y_new][$x_new]) {
            $used[$y_new][$x_new] = true;
            search($x_new, $y_new, $sum + $grid[$y_new][$x_new], $margin + 40);
            $used[$y_new][$x_new] = false;
        }
    }
}

/*$grid = array();
$grid[0] = array(1, 1, 1, 1);
$grid[1] = array(1, 30, 80, 2);
$grid[2] = array(1, 1, 1, 100);*/

$grid = array(array(10, 1, 52), array(20, 30, 1), array(1, 2, 3));

$m = count($grid[0]);
$n = count($grid);
$ans = NO_ANSWER;

$used = array();
for ($y = 0; $y < $n; $y++) {
    $used[$y] = array_fill(0, $m, false);
}
?>
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>剪格子</title>
<style>
body {
    font-family: Arial;
    font-size: 14px;
}
table {
    border-collapse: collapse;
    font-weight: bold;
    margin-bottom: 10px;
    margin-right: 10px;
}
td {
    background-color: pink;
    text-align: center;
    width: 30px;
    height: 30px;
}
td.used {
    background-color: yellow;
}
td.correct {
    background-color: red;
}
</style>
</head>

<body>
<?php
search(0, 0, $grid[0][0]);
?>
<div style="clear:both"><b>最終結果: </b><?=$ans?></div>
</body>
</html>

【純PHP版代碼】
<?php
define('NO_ANSWER', 0xffff);
$GLOBALS['answer'] = NO_ANSWER;

$GLOBALS['grid'] = array(array(1, 1, 1, 1), array(1, 30, 80, 2), array(1, 1, 1, 100)); // 數據

$GLOBALS['m'] = count($grid[0]);
$GLOBALS['n'] = count($grid);

$GLOBALS['used'] = array();
for ($y = 0; $y < $GLOBALS['n']; $y++) {
    $GLOBALS['used'][$y] = array_fill(0, $GLOBALS['m'], false);
}

function calc($used) {
    $result = array('sum' => 0, 'grid_num' => 0);
    for ($x = 0; $x < $GLOBALS['m']; $x++) {
        for ($y = 0; $y < $GLOBALS['n']; $y++) {
            if ($GLOBALS['used'][$y][$x] == $used) {
                $result['sum'] += $GLOBALS['grid'][$y][$x];
                $result['grid_num']++;
            }
        }
    }
    return $result;
}

function search($x, $y, $sum1) {
    $GLOBALS['used'][$y][$x] = true;
   
    $rs = calc(false);
    if ($rs['sum'] == $sum1) {
        $new_answer = $GLOBALS['m'] * $GLOBALS['n'] - $rs['grid_num'];
        if ($GLOBALS['answer'] > $new_answer) {
            $GLOBALS['answer'] = $new_answer;
        }
        return;
    }
   
    $directions = array(array(-1, 0), array(0, -1), array(1, 0), array(0, 1));
    foreach ($directions as $dir) {
        $x_new = $x + $dir[0];
        $y_new = $y + $dir[1];
        if ($x_new >= 0 && $x_new < $GLOBALS['m'] && $y_new >= 0 && $y_new < $GLOBALS['n'] && !$GLOBALS['used'][$y_new][$x_new]) {
            $GLOBALS['used'][$y_new][$x_new] = true;
            search($x_new, $y_new, $sum1 + $GLOBALS['grid'][$y_new][$x_new]);
            $GLOBALS['used'][$y_new][$x_new] = false;
        }
    }
}
?>
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>剪格子</title>
</head>

<body>
<?php
search(0, 0, $GLOBALS['grid'][0][0]);
echo '<b>結果: </b>';
if ($GLOBALS['answer'] == NO_ANSWER) {
    echo 0;
} else {
    echo $GLOBALS['answer'];
}
?>
</body>
</html>

運行結果：
結果: 10

【PHP面向對象版代碼】
<?php
class grid {
    const NO_ANSWER = 0xffff;
   
    public $data = array();
    private $m;
    private $n;
    private $used;
    private $answer;
   
    public function add() {
        array_push($this->data, func_get_args());
    }
   
    public function calc_answer() {
        $this->answer = self::NO_ANSWER;
        if (isset($this->data[0])) {
            $this->m = count($this->data[0]);
            $this->n = count($this->data);
            $this->used = array();
            for ($y = 0; $y < $this->n; $y++) {
                $this->used[$y] = array_fill(0, $this->m, false);
            }
            $this->search(0, 0, $this->data[0][0]);
        }
        return $this->answer;
    }
   
    public function clear() {
        $this->data = array();
    }
   
    private function get_status($used) {
        $status = array('sum' => 0, 'grid_num' => 0);
        for ($x = 0; $x < $this->m; $x++) {
            for ($y = 0; $y < $this->n; $y++) {
                if ($this->used[$y][$x] == $used) {
                    $status['sum'] += $this->data[$y][$x];
                    $status['grid_num']++;
                }
            }
        }
        return $status;
    }
   
    private function search($x, $y, $sum) {
        $this->used[$y][$x] = true;
        $status = $this->get_status(false);
        if ($status['sum'] == $sum) {
            $new_answer = $this->m * $this->n - $status['grid_num'];
            if ($this->answer > $new_answer) {
                $this->answer = $new_answer;
            }
        } else {
            $directions = array(array(-1, 0), array(1, 0), array(0, -1), array(0, 1));
            foreach ($directions as $dir) {
                $x_new = $x + $dir[0];
                $y_new = $y + $dir[1];
                if ($x_new >= 0 && $x_new < $this->m && $y_new >= 0 && $y_new < $this->n && !$this->used[$y_new][$x_new]) {
                    $this->used[$y_new][$x_new] = true;
                    $this->search($x_new, $y_new, $sum + $this->data[$y_new][$x_new]);
                    $this->used[$y_new][$x_new] = false;
                }
            }
        }
    }
   
    public function show_answer() {
        $this->calc_answer();
        echo '<b>結果: </b>';
        if ($this->answer == self::NO_ANSWER) {
            echo 0;
        } else {
            echo $this->answer;
        }
        echo "<br>\n";
    }
}
?>
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<title>剪格子</title>
</head>

<body>
<?php
$g = new grid();
$g->add(1, 1, 1, 1);
$g->add(1, 30, 80, 2);
$g->add(1, 1, 1, 100);
$g->show_answer();

$g->clear();
$g->add(10, 8, 5, 7, 6, 4);
$g->add(1, 9, 6, 2, 3, 5);
$g->add(1, 3, 2, 1, 5, 2);
$g->show_answer();

$h = new grid();
$h->add(10, 1, 52);
$h->add(20, 30, 1);
$h->add(1, 2, 3);
$h->show_answer();
?>
</body>
</html>

【運行結果】
結果: 10
結果: 6
結果: 3