问个世界名画陈列馆的问题
各位大虾，本人算法设计新手，遇到个问题，冥思苦想两个星期没想明白，求教下大家！！
算法设计里面有道名画陈列馆问题，用回溯法解，代码里面有个地方用于剪枝，怎么也想不通，大家看看！
****************************************************************************************
世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4 个陈列室。试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。
设计一个算法，计算警卫机器人的最佳哨位安排，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。
输入：第一行有2 个正整数m和n (1≤m,n≤20)。
输出：文件的第一行是警卫机器人数；接下来的m行中每行n个数，0 表示无哨位，1 表示哨位。
样例输入
4 4
样例输出
4
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
****************************************************************************************
//************************************************************************/
//* 回溯法 */
//************************************************************************/
#include <iostream>
using namespace std;
#define MLEN 20
int n, m, best, k=0, t=0, t1, t2, more;
int d[6][3] = {{0,0,0},{0,0,0},{0,0,-1},{0,-1,0},{0,0,1},{0,1,0}};
int x[MLEN+1][MLEN+1];
int y[MLEN+1][MLEN+1];
int bestx[MLEN+1][MLEN+1];
void change(int i, int j)
{
x[i][j] = 1;
k ++;
for (int s=1; s <=5; s++)
{
int p = i + d[s][1];
int q = j + d[s][2];
y[p][q] ++;
if (y[p][q] == 1)
t ++;
}
}
void restore(int i, int j)
{
x[i][j] = 0;
k --;
for (int s=1; s <=5; s++)
{
int p = i + d[s][1];
int q = j + d[s][2];
y[p][q] --;
if (y[p][q] == 0)
t --;
}
}
void search(int i, int j)
{
do
{
j ++;
if (j>m)
{
i ++;
j = 1;
}
}while(!(y[i][j]==0 || i>n));
if (i>n)
{
if (k <best)
{
best = k;
for (int p=1; p <=n; p++)
for (int q=1; q <=m; q++)
{
bestx[p][q] = x[p][q];
}
}
return;
}
if (k+(t1-t)/5>=best)
{
return;
}
//////////看不懂！///////////////////////////////
if (i <n-1 && k+(t2-t)/5>=best)
{
return;
}
////////////////////////////////////////////////
if (i <n)
{
change (i+1, j);
search (i, j);
restore(i+1, j);
}
if (j <m && (y[i][j+1]==0 || y[i][j+2]==0))
{
change (i, j+1);
search (i, j);
restore(i, j+1);
}
if (y[i+1][j]==0 && y[i][j+1]==0)
{
change (i, j);
search (i, j);
restore(i, j);
}
}
void compute()
{
int i;
//////////看不懂！///////////////////////////////
more = m/4 + 1;
if (m%4 == 3)
more ++;
else if (m%4 == 2)
more += 2;
t2 = m*n + more +4;[/color]
t1 = m*n +4;
/////////////////////////////////////////////////
best = 65536;
if (n==1 && m == 1)
{
cout < <1 < <endl;
cout < <1 < <endl;
return;
}
for (i=0; i <=m+1; i++)
{
y[0][i] = 1;
y[n+1][i] = 1;
}
for (i=0; i <=n+1; i++)
{
y[i][0] = 1;
y[i][m+1] = 1;
}
search(1, 0);
}
int main()
{
while (cin>>n)
{
cin>>m;
k = 0;
for (int i=0; i <=MLEN; i++)
{
for (int j=0; j <=MLEN; j++)
{
x[i][j] = 0;
y[i][j] = 0;
}
}
compute();
cout < <best < <endl;
for (int i=1; i <=n; i++)
{
for (int j=1; j <=m; j++)
{
cout < <bestx[i][j] < <" ";
}
cout < <endl;
}
}
return 0;
}
