蓝桥杯2013年第四届真题-剪格子-题解（C++代码）--笔记

参考代码:

#include<bits/stdc++.h>
using namespace std;
int m, n;
int result = INT_MAX;
int a[11][11];
int flag[11][11];
int dir[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };//左上右下；

bool in(int x, int y)
{
	return (x >= 0 && x < n&& y >= 0 && y < m);
}
void dfs(int x, int y, int sum)
{
	sum += a[x][y];
	flag[x][y] = 1;
	int o_sum = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (flag[i][j] ==0) o_sum+=a[i][j];
		}
	}
	if (o_sum == sum)
	{
		int k = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (flag[i][j] == 1)  k++;
			}
		}
		if (k < result) result = k;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int dx = x + dir[i][0];
		int dy = y + dir[i][1];
		if (in(dx, dy) && flag[dx][dy] == 0) dfs(dx, dy, sum);
	}
	flag[x][y] = 0;
}
int main()
{
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}
	dfs(0, 0, 0);
	cout << result;
}