鏈接:
http://poj.grids.cn/practice/2814
這個題目可以枚舉或者直接暴力。但是,這之前必須弄明白答案的解空間。。。也就是解可能的情況。。。很簡單,一共有9種移動方案。也很了然的知道對于某種方案使用N次的效果等同于N%4的效果,也就是說某種方案只可能使用0,1,2,3次。。。一共有9種方案,那么一共就只有4^9種可能的解。。。這么小的解空間,無論用什么方法都不會超時了。。。暴力可以才用9重循環(huán),或者深搜,當時覺得寫9重循環(huán)是件很糗的事情,就果斷深搜了。。。
如果這題才用枚舉的方法的話,思考方式還是那樣先確定假設(shè)解的部分情況,通過已經(jīng)知道的規(guī)則確定解的其它情況,然后求出這個解,判斷這個解是否滿足題目要求。。。比如,我們可以枚舉1,2,3號方案的情況,根據(jù)規(guī)則確定其它方案的使用情況,求出所有方案的使用情況后,判斷假設(shè)的解是否滿足要求就可以了...
我才用的是dfs+剪枝,這個題目其實題意或者說答案有誤,因為答案是搜索找到第一個解,而不是所謂的最短序列的解,當然如果數(shù)據(jù)使得2者都是一樣的話,那么題意就無誤了...我的代碼是假設(shè)找到的第一個就是最短序列的,這種情況下才能使用剪枝,因為找到一個解后就不需要繼續(xù)找了...
代碼如下:
#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得實在無語了...今天晚上檢查才突然發(fā)現(xiàn)的...
這半個多月做了60道題了,都沒有改動這低級的bug習(xí)慣...實在無語...遞歸,回溯,剪枝都寫上了...唉...實在無語...還不如直接9重循環(huán),多省心...真不該歧視某種方法的...