8.31日-9.2日做的搜索练习总结
wpl13112682 · · 个人记录
8.31日-9.2日做的搜索练习总结
P1331 海战： 给定一个矩阵，矩阵包含 # 和 . 。#表示船只，. 表示水。要在图中找到有几个完整的矩形。船的位置摆放正确（即棋盘上只存在相互之间不能接触的矩形，如果两个#号上下相邻或左右相邻却分属于不同的船只，则两艘船互相接触，对角接触不算），输出图中有几艘船。
思路：从左到右，从上到下遍历整个图，若找到一个#，且这个#没有被搜到过，那么就进入递归，记#坐标为x，y。先在x这一行找到连续#结束的列坐标y1，然后从x+1行开始，往下搜索最大完整矩形结束的位置x2，y2。然后在找出的矩形周围遍历，判断是否有#出现。若#出现，找到的矩形不合法，输出No。若#没出现，找到的矩形数+1，退出。
我在递归的时候，出现的问题有：①找到y1的值用的for循环，导致判断for循环退出边界判断出了问题。这个时候用while循环不停的判断当前x1，y1的下一个x1，y1+1是否是#，更不容易出错。
for循环：
for(int i=y1+1;i<=c;i++){
if(mp[x1][i]=='.'){
for(int j=y;j<=y1;j++) b[x1][i]=1;
break;
}
y1=i;
}while循环：
while(mp[x1][y1+1]=='#'){//只要坐标的右边一个是#，就y1+=y1+1
y1++;
b[x1][y1]=1;}
②还是在for循环找y1的值时，需要标记找到的#，第二层来标记for循环列举范围写错，半天没发现。
for(int j=y;j<=y1;j++) b[x1][i]=1;③在写的过程中，应该用纸笔记下自己的思路和流程图，方便在写程序的时候提醒自己应该做什么，让自己的思路不混乱。
④矩形最后的坐标找错了。
f=0;//f用来标记是否遇到‘.’,如果遇到.这个符号就停止继续向下探索矩形
for(int i=x;i<=r;i++){
if(f) break;
for(int j=y;j<=y1;j++){
if(f) break;
b[i][j]=1;
if(mp[i][j]=='.'){
f=1;
break;
}
x2=i;
y2=j;//x2，y2用来记录搜索到的合法矩形的最右下角的坐标
}
}递归：
void dfs(int x,int y){//搜索以当前坐标（x，y）为起点的矩形是否合法
b[x][y]=1;
int x1,y1,x2,y2;//x1,y1用来记录第一行最右边的#位置
x1=x;
y1=y;
/*while(mp[x1][y1+1]=='#'){//只要坐标的右边一个是#，就y1+=y1+1
y1++;
b[x1][y1]=1;
}*/
for(int i=y1+1;i<=c;i++){
if(mp[x1][i]=='.'){
for(int j=y;j<=y1;j++) b[x1][i]=1;
break;
}
y1=i;
}
f=0;//f用来标记是否遇到‘.’,如果遇到.这个符号就停止继续向下探索矩形
for(int i=x;i<=r;i++){
if(f) break;
for(int j=y;j<=y1;j++){
if(f) break;
b[i][j]=1;
if(mp[i][j]=='.'){
f=1;
break;
}
x2=i;
y2=j;//x2，y2用来记录搜索到的合法矩形的最右下角的坐标
}
}
for(int i=x;i<=x2;i++){
if(mp[i][y-1]=='#'||mp[i][y2+1]=='#'){
t=1;
break;
}
}
for(int i=y;i<=y2;i++){
if(mp[x-1][i]=='#'||mp[x2+1][i]=='#'){
t=1;
break;
}
}
if(!t) ans++;
return ;}
P1057 传球游戏 n个同学站成一个圆，从编号为1的同学开始向相邻的同学传球，左右任意，求在传完m次后，共有多少种方案能使球传回编号为1的同学手中。
思路：递归设置两个变量，当前传球的次数，当前球传到同学的序号。因为n个同学围成了一个圆，所以递归的时候需要注意特判，当序号为1时，和序号为n时的情况。
优化：①判断当前剩余的步数是否还能够让球往左或往右走到1。 ②记忆化搜索。设置一个二维数组b[x][y]，代表当走到第x个节点并且步数为y步时，能有多少种方法走到1位置。需要注意，将b的初始值设为-1。如果将b的初始值设为0，那么在搜索的过程中容易忽略部分实际上没有被搜过的数。
没有优化①：
void dfs(int ceng,int xu){
if(ceng==m&&xu==1){
ans++;
return ;
}
if(ceng>m) return ;
if(xu==1) {
dfs(ceng+1,n);
dfs(ceng+1,xu+1);
}
else if(xu==n) {
dfs(ceng+1,1);
dfs(ceng+1,xu-1);
}
else {
dfs(ceng+1,xu+1);
dfs(ceng+1,xu-1);
}
return ;}
没有优化②：
void dfs(int ceng,int xu){
if(m-ceng<xu-1&&m-ceng<n-xu+1){
return ;
}
if(ceng==m&&xu==1){
ans++;
return ;
}
if(ceng>m) return ;
if(xu==1) {
dfs(ceng+1,n);
dfs(ceng+1,xu+1);
}
else if(xu==n) {
dfs(ceng+1,1);
dfs(ceng+1,xu-1);
}
else {
dfs(ceng+1,xu+1);
dfs(ceng+1,xu-1);
}
return ;}
完全优化：
long long dfs(long long ceng,long long xu){
if(m-ceng<xu-1&&m-ceng<n-xu+1) return 0;
if(ceng==m&&xu==1){
return 1;
}
if(ceng>m) return 0;
if(b[ceng][xu]!=-1) return b[ceng][xu];
long long cnt=0;
if(xu-1<1) {
cnt+=dfs(ceng+1,n);
}
else cnt+=dfs(ceng+1,xu-1);
if(xu+1>n) {
cnt+=dfs(ceng+1,1);
}
else cnt+=dfs(ceng+1,xu+1);
b[ceng][xu]=cnt;
return cnt;}
递归的过程中，返回的值把cnt赋值，当当前状态所有的情况被搜完的时候，就将cnt最终的值赋给b数组。
P7700 燃料收集：
有n个星球，每个星球都有对应的燃料存储值和前往这颗星球需要的燃料值。同一颗星球只能去一次。a为星球上燃料存量，b为去这颗星球需要的燃料量。现在给定小分队的初始星球P，求能收集到的最大燃料数量以及收集最大燃料量能去的最多星球数。
思路：预处理：设一个c，存储最终能在这颗星球上获得的燃料值。因为要使收集到的燃料最大，所以将c为负数的星球直接pass掉，标为0。 然后将结构体数组，以c的大小，从大到小排序。每次从左到右扫一遍结构体数组，加上能去，并且没被标记过的星球燃料。当扫一遍以后最终值没有变化，退出while循环。 预处理：
int n,p,ans,tot=1,t;
struct node{
int a,b,c,mark;}e[N];
bool cmp(node a,node b){
return a.c>b.c;} int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>p;
for(int i=0;i<=n;i++) e[i].mark=1;
for(int i=1;i<=n;i++){
cin>>e[i].a>>e[i].b;
e[i].c=e[i].a-e[i].b;
if(e[i].c<0) e[i].mark=0;
}
ans=e[p].a;
e[p].mark=0;从左至右扫结构体数组：
int f=1,f1;
while(f){
f1=0;
for(int i=1;i<=n;i++){
if( e[i].b<=ans && e[i].mark!=0){
f1=1;
e[i].mark=0;
ans+=e[i].c;
tot++;
}
}
if(f1==0) f=0;
}在判断最终答案是否在这一次遍历时有变动，我直接还给老师了（无语）。只需要设置一个flag=1，若最终值变动了，那么flag=0，在for循环外面判断就行了。