链接:
http://poj.grids.cn/practice/2814
这个题目可以枚举或者直接暴力。但是,这之前必须弄明白答案的解空间。。。也就是解可能的情况。。。很简单,一共有9种移动方案。也很了然的知道对于某种方案使用N次的效果等同于N%4的效果,也就是说某种方案只可能使用0,1,2,3次。。。一共有9种方案,那么一共就只有4^9种可能的解。。。这么小的解空间,无论用什么方法都不会超时了。。。暴力可以才用9重循环,或者深搜,当时觉得写9重循环是件很糗的事情,就果断深搜了。。。
如果这题才用枚举的方法的话,思考方式还是那样先确定假设解的部分情况,通过已经知道的规则确定解的其它情况,然后求出这个解,判断这个解是否满足题目要求。。。比如,我们可以枚举1,2,3号方案的情况,根据规则确定其它方案的使用情况,求出所有方案的使用情况后,判断假设的解是否满足要求就可以了...
我才用的是dfs+剪枝,这个题目其实题意或者说答案有误,因为答案是搜索找到第一个解,而不是所谓的最短序列的解,当然如果数据使得2者都是一样的话,那么题意就无误了...我的代码是假设找到的第一个就是最短序列的,这种情况下才能使用剪枝,因为找到一个解后就不需要继续找了...
代码如下:
#include <stdio.h>
int nMinTimes;
int nPath[40];
bool bFind = false;
char* szMoves[10] =
{
NULL,
"ABDE",
"ABC",
"BCEF",
"ADG",
"BDEFH",
"CFI",
"DEGH",
"GHI",
"EFHI"
};
bool IsPosOK(int* nPos)
{
for (int i = 0; i < 9; ++i)
{
if (nPos[i])
{
return false;
}
}
return true;
}
void Move(int nChoose, int nTimes, int* nPos)
{
if (nTimes > 0)
{
char* pszStr = szMoves[nChoose];
while (*pszStr)
{
nPos[*pszStr - 'A'] = (nPos[*pszStr - 'A'] + nTimes) % 4;
++pszStr;
}
}
}
void MoveBack(int nChoose, int nTimes, int* nPos)
{
if (nTimes > 0)
{
char* pszStr = szMoves[nChoose];
while (*pszStr)
{
nPos[*pszStr - 'A'] = (nPos[*pszStr - 'A'] - nTimes + 4) % 4;
++pszStr;
}
}
}
void Cal(int nChoose, int* nPos, int* nUsed, int nUsedTimes)
{
if (nChoose == 10)
{
if (IsPosOK(nPos) && !bFind)
{
nMinTimes = nUsedTimes;
for (int i = 0; i < nMinTimes; ++i)
{
nPath[i] = nUsed[i];
}
bFind = true;
}
return;
}
for (int i = 0; i <= 3; ++i)
{
Move(nChoose, i, nPos);
for (int j = 0; j < i; ++j)//放入i次的nChoose
{
nUsed[nUsedTimes + j] = nChoose;
}
if (!bFind)
{
Cal(nChoose + 1, nPos, nUsed, nUsedTimes + i);
}
MoveBack(nChoose, i, nPos);
}
}
int main()
{
int nPos[9];
int nUsed[40];
for (int i = 0; i < 9; ++i)
{
scanf("%d", &nPos[i]);
}
Cal(1, nPos, nUsed, 0);
for (int i = 0; i < nMinTimes; ++i)
{
printf("%d", nPath[i]);
if (i != nMinTimes - 1)
{
putchar(' ');
}
else
{
putchar('\n');
}
}
return 0;
}
这道题其实我wa了近10次,原因就是Move和MoveBack写错了,没有移动nTimes次,而前面一直写成了1,昨晚wa得实在无语了...今天晚上检查才突然发现的...
这半个多月做了60道题了,都没有改动这低级的bug习惯...实在无语...递归,回溯,剪枝都写上了...唉...实在无语...还不如直接9重循环,多省心...真不该歧视某种方法的...