[蓝桥杯][2013年第四届真题]剪格子

题目

题目链接

题解

DFS。

为啥不能用BFS？ BFS的话，每扩展一个结点之前扩展过的结点都要被标记，但是其实并不能将队列中出现过的结点都标记，只用标记扩展到当前结点所在路径上的结点即可。多余的扩展会影响结果的正确性，导致有些要走的点没法走了。而用BFS很难在扩展结点时只标记其祖宗结点，因此我们采用DFS。

模板题吧。 注意先输入列数再输入行数，我他妈卡了好一会。

额外说几句，就是蓝桥杯的题本身就不严谨，准确的说很垃圾，无论是题目描述还是数据都水的一批。所以，既然AC了就不要再考虑什么哪些样例过不去什么的，没意义，那说明它这道题就没想卡你那个样例，就是让你按照这个可能有错的思路去实现。

我看有人说泛洪（Flood-Fill），确实泛洪算法更适合解这个题，但题目不也说”如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目“，如果泛洪出的结果中满足的都不包含左上角的格子呢？对吧没必要非要保证每个样例都过，说不定你写的代码还忘了考虑其中一个输入为0的情况嘞。

归根到底，lj LQB！

代码

#include
using namespace std;
const int N = 100, INF = 1e9;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int n, m, sum, ans = INF;
int a[N][N], vis[N][N];

void dfs(int x, int y, int s, int step) {
	
	if(s > sum/2 || step > ans) return ; // 小剪枝
	if(s == sum/2) {ans = min(ans, step); return ;}
	
	for(int i = 0;i >m>>n; // 注意先输入的是列，后输入行 
	for(int i = 1;i a[i][j], sum += a[i][j];
	
	if((sum&1) || !n || !m) {cout