2636: 回溯法-世界名画陈列馆问题

#include <stdio.h>

int m,n; //全局变量分别表示世界名画陈列馆中有m行n列个陈列室

int bestx[12][12]; //存储最优解，0号单元不用
int x[12][12]; //存储当前解，0号单元不用

int y[12][12]; //表示世界名画陈列馆中的陈列室受到机器人监控的次数

int bestNumber, currentNumber; //全局变量分别表示递归过程中当前找到的最优值以及当前值

void change(int i, int j) {
	x[i][j]=1;
	y[i][j]++;
	y[i-1][j]++;
	y[i+1][j]++;
	y[i][j-1]++;
	y[i][j+1]++;
	currentNumber++;
}

void restore(int i, int j) {
	x[i][j]=0;
	y[i][j]--;
	y[i-1][j]--;
	y[i+1][j]--;
	y[i][j-1]--;
	y[i][j+1]--;
	currentNumber--;
}

void Backtrack(int i, int j) {
	while (y[i][j]!=0 && i<=m) {  //如果已经受到监视，则不放哨兵
		j++;
		if (j>n) { //从下一行开始
			i++;
			j=1;
		}
	}
	if (i>m) { //递归出口,更新最优解和最优值
		for(int ii=1; ii<=m; ii++) {
			for (int jj=1; jj<=n; jj++) {
				bestx[ii][jj]=x[ii][jj];
			}
		}
		bestNumber = currentNumber;
	} else { //分为三种情况：(i+1,j),(i,j),(i,j+1)

		if (i<m && currentNumber<bestNumber) {// case1
			
		}
		if (currentNumber<bestNumber) {// case2
			 
		}
		if (j<n && currentNumber<bestNumber) { //case3
			
		}
	}	
}

void init() {
	int i,j;
	bestNumber=m*n; // 机器人数量不可能超过陈列室的个数
	currentNumber=0;
	for(j=0; j<=n+1; j++) {// 简化边界条件，假设存在第0行和第m+1行陈列室且已经受到监控
		y[0][j]=1;
		y[m+1][j]=1;
	}
	for(i=0; i<=m+1; i++) {// 简化边界条件，假设存在第0列和第n+1列陈列室且已经受到监控
		y[i][0]=1;
		y[i][n+1]=1;
	}
	for(i=1; i<=m; i++) {
		for(j=1; j<=n; j++) {
			y[i][j]=0;  //初始化世界名画陈列馆中的所有陈列室没有受到监控
		}
	}
}

int main(void) {
	scanf("%d %d",&m,&n);
	init();
	Backtrack(1,1);
	printf("%d\n", bestNumber);
	return 0;
}

4 4

4