搜索过程中记录改变方向的次数

其实，题目很简单，就是类似于给你一个二维矩阵，求从A到B的转的次数最小是多少。附加条件就是这个过程之中会有一些障碍物，你不能通过，也可以设定这个过程之中只能往哪个方向走，当然，这不是这题的限制条件。
先来整理以下bfs的思路吧，bfs就是将你要走的点分成几个不同的层次，某些点在同一个层次，然后，你按照顺序，将每一层的点遍历之后才能遍历下一层的点，然后逐层判断所求结果即可，通常的方法就是放到一个队列queue里面保存，然后按照顺序进行遍历。
对于dfs的思路，就是往深处遍历，你每走到某一个点，你可以选择选这个点或者不选这个点，对于选择或者不选择这个点，都会有不同的结果，然后按照答案对应选择，这里面，可能会有需要减枝的情况。比如在某一个点的情况下，不是目前已经所知道的最优的解，或者是与目前已知的最优的解相矛盾，那么就可以直接选择返回上一层继续搜索。
对于两种不同的搜索，其实他们的实质都是共同的，就是通过让局部的结果最优化，然后得到最终的结果，两种的搜索都是首先要进行边界的处理，要找出递归结束的边界。同时还要进行判断合适可以返回上一层的条件。这大体就是搜索的基本框架。
言归正传，再回到这一题目来，我们通常都是做的事寻求最短的步骤的题目，突然来了个如何找出最少的转弯次数的话，思路：我们要判断我们我们每走到某一个点的时候，这个时候的方向，然后与下一步骤的方向进行比较判断，进行记录在那一步的最优的解，不断更新。
在这里，有几个比较巧妙地方法，就是将二维矩阵地每一个点都用一个数组来进行存储，（这要适用于矩阵比较小地情况），然后我们在搜索的过程之中，用一个vis数组记录某一个位置pos（其实是一个二维矩阵之中的点）的局部最优解，一层一层的递推过去即可。同时，我们将横竖当作两个不同的方向，然后dfs的参数就是我们当前遍历的位置，
pos，当前的方向dir，当前的最优的解num，然后注意递归的边界。同时，由于有4个方向，所以我们可以判断方向是否相同，然后根据方向进行不断地更新那三个量。
代码如下：

#include<iostream>
#include<cstring>
using namespace std;
const int N=1000010;
char a[N];
bool inq[N]={false};
int vis[N];
int A,B,ans=1e9;
int n;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void dfs(int pos,int dir,int num){
    if(pos==B)  ans=min(ans,num);
    if(inq[pos])  return;
    inq[pos]=true;
    for(int i=0;i<4;i++){
        int x=pos/1000+dx[i];
        int y=pos%1000+dy[i];
        int pos_new=x*1000+y;
        if(a[pos_new]=='x')  continue;
        if(x<1||y<1||x>n||y>n)  continue;
        if((i==1||i==0)&&dir!=0){
            if(vis[pos_new]>=num+1){
                vis[pos_new]=num+1;
                dfs(pos_new,0,num+1);
            }
        }
        else if((i==2||i==3)&&dir!=1){
            if(vis[pos_new]>=num+1){
                vis[pos_new]=num+1;
                dfs(pos_new,1,num+1);
            }
        }
        else{
            if(vis[pos_new]>=num){
                vis[pos_new]=num;
                dfs(pos_new,dir,num);
            }
        }
    }
    inq[pos]=false;
}
int main(){
    cin>>n;
    ans=N;
    memset(vis,N,sizeof(vis));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int pos=1000*i+j;
            cin>>a[pos];
            if(a[pos]=='A')  A=pos;
            else if(a[pos]=='B')   B=pos;
        }
    }
    vis[A]=0;
    dfs(A,2,0);
    if(ans==N)  cout<<"-1" <<endl;
    else  cout<<ans-1<<endl;
    return 0;
}