1189 SEARCH
一、用普通深搜
这是洛谷唯一一个迭代加深的题目，真的是太少了，用它来练练手
这个问题的求解思路就是说按照它所给的方向进行一个搜索，而不是我们一贯的使用上下左右的顺序了，这就是我之前和zqc问的一样，分题而异，这个题就得按照所给方向
搜索函数，第一次从小偷位置开始，每次获取当前所在点的坐标，然后枚举所给的方向d，实现预备好方位数组，然后判度递归并且不能为’X‘，接着递归，坐标加上方位数组
这里的获取方位数组，比较巧妙，枚举四个方位到底是哪一个方向，然后返回0 1 2 3，根据这个在找到事先准备的方位数组
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};//枚举四个方向
int r,c;int n;
int sx,sy;
int b[65][65][1005];
char d[1005][15];
char a[65][65];
inline void read()
{cin>>r>>c;for(int i=1;i<=r;i++)cin>>a[i]+1;cin>>n;for(int i=1;i<=n;i++){cin>>d[i];}for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){if(a[i][j]=='*'){sx=i;sy=j;break;}}}a[sx][sy]='.';
}
int go(char x)
{//判断方位 if(x == 'N')//上 return 2;if(x == 'S')//下 return 0;if(x == 'E')//左 return 1;if(x == 'W')//右 return 3;}
bool pd(int x,int y)
{//判断越界函数 return x<=r&&y<=c&&x>0&&y>0;}
void dfs(int x,int y,int s)
{if(b[x][y][s])return ;b[x][y][s]=1;if(s==n+1)//边界 {a[x][y]='*';return ;}else{int ex=x,ey=y;p=go(d[s][0]);ex+=dx[p];ey+=dy[p];while(pd(ex,ey)&&a[ex][ey]!='X'){dfs(ex,ey,s+1);//递归方向ex+=dx[p];ey+=dy[p]; }}}
int main()
{read();dfs(sx,sy,1);//从小偷的位置出发 for(int i=1;i<=r;i++){cout<<a[i]+1<<endl;}return 0;
}
二、用迭代加深搜索
题目大意我们都已经知道了，直接说思路了
迭代加深的思想：
1.先制定一个小目标，搜索的深度不超过1层，看看能不能搜到答案
2.如果不行，就把搜索深度设置为2，看能不能找到
3.如果不行，就把搜索深度设置为3，看能不能找到
直到设置成p，找到答案为止
个人理解的迭代加深就是枚举加上循环
经过3天的训练，终于把这道题 做出来了，真的是好棒。首先我先说明一下在写代码的时候，注意定义变量的时候map，ch这两个变量，因为这两个变量都在库存过，会起冲突了，因为这个我调了两个小时
首先我们定义一个数组a[i][j]表示(i,j)这个点由a[i][j]步到达，所以一开始的起点（*）就是a[i][j]=1，到达不了的点（X）就是a[i][j]=-1，其他的点就是a[i][j]=0
那么在这里运用的迭代加深的思想就很明显了，迭代是指的q步数，而加深就是说的移动，也就是上左下右的移动
迭代，所以我们一开始的时候输入时候将a数组初始化，然后枚举q个步数，接着判断是否到达了一个新的限制，进行重新搜索，枚举四个方向，上左下右（NSWE）的搜索直至搜索到了边界或者不能到达的点，就要停下来了，继续新的迭代搜索
加深，接下来的加深其实就没有运用到递归搜索这个算法，只是按着这个方向一直循环搜索，一直到边界或者不能到达的点（X），记得保存a数组的步数
最后就是输出，判断最后的步数，如果q+1步说明可以到达，输出即可
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int q;
int a[65][65];//a[i][j]数组记录（i，j）位置由a[i][j]步到达
char cch[11];
char mapp[55][55];
bool pd(int x,int y)
{return x>=0&&x<n&&y>=0&&y<m;
}
void shang(int x,int y,int id)
{while(pd(x,y)&&mapp[x][y]!='X'){a[x][y]=id+1;x--;//一直向上 }
}
void xia(int x,int y,int id)
{while(pd(x,y)&&mapp[x][y]!='X'){a[x][y]=id+1;x++;//一直向下 }
}
void zuo(int x,int y,int id)
{while(pd(x,y)&&mapp[x][y]!='X'){a[x][y]=id+1;y--;//一直向左 }
}
void you(int x,int y,int id)
{while(pd(x,y)&&mapp[x][y]!='X')//循环模拟递归 {a[x][y]=id+1;y++;}
}
void go(int id,char chh[])
{//迭代加深 for(int i=0;i<n;i++){for(int j=0;j<m;j++){//重复，重复 的过程不浪费时间吗？ if(a[i][j]==id)//到达搜索层 {if(cch[0]=='N') shang(i-1,j,id);else if(cch[0]=='S') xia(i+1,j,id);else if(cch[0]=='W') zuo(i,j-1,id);else you(i,j+1,id);//模拟四个方向，加深搜索 }}}
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++)cin>>mapp[i];for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mapp[i][j]=='X') a[i][j]=-1;//不能走 else if(mapp[i][j]=='*') a[i][j]=1;//起点一步到达 }}cin>>q;for(int id=1;id<=q;id++)//将问题分解成q步 {cin>>cch;//迭代加深p层搜索 go(id,cch);//限制搜索层数为id }for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mapp[i][j]=='X') cout<<'X';//到达死胡同 else if(a[i][j]==q+1) cout<<'*';//q步可以到达 else cout<<'.';}cout<<endl;} return 0;
}//自古忠孝难两全，金甲何许家团圆
