又來說搜索
如果我們不好確定搜索的結束條件，那么我們可以假設一下他的搜索深度。
將這個深度取到極限就可以了。
也就是說，如果當小于這個深度有解了，那么停止搜索，得到答案；
如果等于這個深度了，還沒有解，那么我們就認為此種情況下無解，也停止
搜索，也算是得到了答案，即無解。
下面來看一個很簡單的例子吧。題目：http://acm.swust.edu.cn/oj/problem/0823/
View Code
#include "iostream"
#include "cstdio"
#include "cstring"
#include "string"
#include "algorithm"
using namespace std;
int ans;
int Dir[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
char Map[11][11];
struct Pos
{
int x, y;
};
Pos Cat, Mou, TC, TM;
int DFS(Pos C, Pos M, int DirC, int DirM, int Depth)
{
if(Depth==0) return 0;
ans++;
if(C.x==M.x && C.y==M.y) return ans;
DirC %= 4; DirM %= 4;
TC.x = Dir[DirC][0]+C.x;
TC.y = Dir[DirC][1]+C.y;
TM.x = Dir[DirM][0]+M.x;
TM.y = Dir[DirM][1]+M.y;
if(TC.x>=0 && TC.y>=0 && TC.x<10 && TC.y<10 && Map[TC.x][TC.y]!='*' && TM.x>=0 && TM.y>=0 && TM.x<10 && TM.y<10 && Map[TM.x][TM.y]!='*')
DFS(TC, TM, DirC, DirM, Depth-1);
else if(((TC.x>=0 && TC.y>=0 && TC.x<10 && TC.y<10 && Map[TC.x][TC.y]=='*') ||TC.x<0 || TC.y<0 || TC.x>=10 || TC.y>=10 ) && TM.x>=0 && TM.y>=0 && TM.x<10 && TM.y<10 && Map[TM.x][TM.y]!='*' )
DFS(C, TM, DirC+1, DirM, Depth-1);
else if(TC.x>=0 && TC.y>=0 && TC.x<10 && TC.y<10 && Map[TC.x][TC.y]!='*' && ((TM.x>=0 && TM.y>=0 && TM.x<10 && TM.y<10 && Map[TM.x][TM.y]=='*') || TM.x<0 || TM.x>=10 || TM.y<0 || TM.y>=10) )
DFS(TC, M, DirC, DirM+1, Depth-1);
else if(((TC.x>=0 && TC.y>=0 && TC.x<10 && TC.y<10 && Map[TC.x][TC.y]=='*') ||TC.x<0 || TC.y<0 || TC.x>=10 || TC.y>=10 ) && ((TM.x>=0 && TM.y>=0 && TM.x<10 && TM.y<10 && Map[TM.x][TM.y]=='*') || TM.x<0 || TM.x>=10 || TM.y<0 || TM.y>=10) )
DFS(C, M, DirC+1, DirM+1, Depth-1);
}
int main()
{
for(int i=0; i<10; i++)
for(int j=0; j<10; j++)
{
cin>>Map[i][j];
if(Map[i][j]=='C')
{
Cat.x = i;
Cat.y = j;
}
if(Map[i][j]=='M')
{
Mou.x = i;
Mou.y = j;
}
}
ans = -1;
cout<<DFS(Cat, Mou, 0, 0, 1000)<<endl;
}
posted on 2012-03-23 22:08 More study needed. 閱讀(176) 評論(0) 收藏 舉報
浙公網安備 33010602011771號