再次說搜索
這次說的又有點新鮮的東西。
那就是回溯了。
本題是一個經典回溯例題,注意體會一下OK,
那么我們說說他有什么用呢?
其實很簡單了,它的作用就是控制DFS的搜索流程。
在本題簡單一點來說,就是它能使得DFS符合題意。
直接看例子吧。
題目:HDU 1045 http://acm.hdu.edu.cn/showproblem.php?pid=1045
題意:這個是一個八皇后的變種。不算難。
Sample Input:
4
.X..
....
XX..
....
Sample Output:
5
View Code
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
char Map[5][5];
int N, Max;
bool OK(int x, int y)
{
int i, j;
for(i=x-1; i>=0; i--)
{
if(Map[i][y]=='N') return false;
else if(Map[i][y]=='X') break;
}
for(j=y-1; j>=0; j--)
{
if(Map[x][j]=='N') return false;
else if(Map[x][j]=='X') break;
}
return true;
}
void DFS(int Pos, int C)
{
if(Pos==N*N)
{
if(C>Max) Max=C;
return;
}
int i=Pos/N, j=Pos%N;
if(Map[i][j]=='.' && OK(i, j))
{
Map[i][j]='N';
DFS(Pos+1, C+1);
Map[i][j]='.'; //回溯 回溯 回溯 回溯
}
DFS(Pos+1, C);
return;
}
int main()
{
int i, j;
while(cin>>N && N)
{
for(i=0; i<N; i++)
for(j=0; j<N; j++)
cin>>Map[i][j];
Max = 0;
DFS(0, 0);
cout<<Max<<endl;
}
}
posted on 2012-03-26 22:39 More study needed. 閱讀(212) 評論(0) 收藏 舉報

浙公網安備 33010602011771號