蓝桥杯历届试题-剪格子 （C++代码）

解题思路:典型深搜





注意事项:
注意先输入列再输入行

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
struct Node {
	int status = 0;
	int value = 0;
}visit[10][10];
int dfs(int, int, int, int);
int count = 0;
int counter = 0;
int num[50];
int r, c;
int min1 = 10000;
int deep;
int main() {
	cin >> c >> r;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> visit[i][j].value;
			counter += visit[i][j].value;
		}
	}
	dfs(0, 0, 0, 1);
	if (min1 == 10000) {
		cout << 0;
		return 0;
	}
	cout << min1;
	return 0;
}
int dfs(int x, int y, int count, int deep) {
	if (visit[x][y].status == 1) {
		return 0;
	}
	visit[x][y].status = 1;
	count += visit[x][y].value;
	if (count == counter/2) {
		if (deep < min1) {
			min1 = deep;
		}
		return 1;
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (i == x + 1 && j == y&&visit[i][j].status == 0 && visit[i][j].value + count <= counter) {
				dfs(i, j, count, deep + 1);
			}
			if (i == x && (j == y + 1 || j == y - 1) && visit[i][j].status == 0 && visit[i][j].value + count <= counter) {
				dfs(i, j, count, deep + 1);
			}
			if (i == x - 1 && j == y&&visit[i][j].status == 0 && visit[i][j].value + count <= counter) {
				dfs(i, j, count, deep + 1);
			}
		}
	}
	visit[x][y].status = 0;
	count -= visit[x][y].value;
	return 0;
}