记忆化搜索 uva-10651-Pebble Solitaire
题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1592
题目意思:
给一串-和o组成的字符串，你可以把“-oo"变成”--o"，可以把“oo-”变成“--o",问最后最少有多少个o.
解题思路：
采用记忆化搜素的方法，用map标记是否访问过，用string的substr提取连续的三个字符，用string的replace得到替换后的字符串。
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;map<string,bool>mymap;int ans;void dfs(string cur){ if(mymap.find(cur)!=mymap.end()) //如果已经检查了 return ; int len=cur.size(),num=0; for(int i=0;i<len;i++) //查看o的数量 if(cur[i]=='o') num++; if(num<ans) ans=num; mymap[cur]=true; //把当前状态放到map里 for(int i=0;i<=len-3;i++) { if(cur.substr(i,3)=="-oo") //如果有-oo出现，则可以调换 { string temp=cur; temp.replace(i,3,"o--"); dfs(temp); } if(cur.substr(i,3)=="oo-") { string temp=cur; temp.replace(i,3,"--o"); dfs(temp); } } return ;}int main(){ int n; scanf("%d",&n); string temp; while(n--) { map<string,bool>::iterator begin=mymap.begin(); map<string,bool>::iterator end=mymap.end(); mymap.erase(begin,end); //把当前的map清空 ans=INF; cin>>temp; dfs(temp); printf("%d\n",ans); } return 0;}