迭代加深,双向搜索,IDA*,A*,双端队列BFS

迭代加深:

//迭代加深搜索
//给搜索设定一个范围,如果在这个范围内没有答案那么再加大搜索范围
//这么做是为了防止搜索过深,导致利用大量时间搜索无用信息
//如果当前搜索是第10位,搜索的是个二叉树,那么前9个就是2^0+2^1+2^2+..+2^9=2^10-1,所以时间复杂度并没增大太多
 
//https://www.acwing.com/problem/content/172/

#include<bits/stdc++.h>
using namespace std;
const int N=500;
int path[N],n;
bool dfs(int now,int max_)
{
    if(now>max_) return false;
    if(path[now]==n) return true;
    bool vis[N]={0};
    for(int i=now;i>=1;i--) //剪枝,从大到小搜,可以更快到达目标值
        for(int j=i;j>=1;j--){
            int num=path[i]+path[j];
            if(vis[num]||num<=path[now]||num>n) continue;
            vis[num]=true,path[now+1]=num;
            if(dfs(now+1,max_)) return true;
        } 
    return false;
}
int main()
{
    path[1]=1; 
    while(cin>>n,n){
        int dep=1;
        while(!dfs(1,dep)) dep++;
        for(int i=1;i<=dep;i++) cout<<path[i]<<' ';
        cout<<endl;
    }
    return 0;
}

双端队列-BFS优化搜索(适合0 1状态):

// https://www.luogu.com.cn/problem/P4667

//94 dijkstra
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
bool vis[N];
int n,m,dist[N];
typedef pair<int,int>pii;
int e[N],ne[N],h[N],idx,w[N];
void add(int a,int b,int c)
{
    w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dijkstra()
{
    priority_queue<pii,vector<pii>,greater<pii> >que;
    que.push({0,1}),dist[1]=0;
    while(!que.empty()){
        pii now=que.top(); que.pop();
        int x=now.second,y=now.first;
        if(vis[x]) continue; vis[x]=true;
        for(int i=h[x];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>y+w[i]){
                dist[j]=y+w[i];
                que.push({dist[j],j});
            }
        }
    }
    return (dist[(n+1)*(m+1)]<0x3f3f3f3f/2);
}
int main() 
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=(n+1)*(m+1);i++) dist[i]=0x3f3f3f3f,h[i]=-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char x; cin>>x;
            if(x=='/'){
                int u=(m+1)*(i-1)+j+1,v=(m+1)*i+j;
                int u_=u-1,v_=v+1;
                add(u,v,0),add(v,u,0),add(u_,v_,1),add(v_,u_,1);
            }
            else{
                int u=(m+1)*(i-1)+j,v=(m+1)*i+j+1;
                int u_=u+1,v_=v-1;
                add(u,v,0),add(v,u,0),add(u_,v_,1),add(v_,u_,1);
            }
        }
    if(dijkstra()) cout<<dist[(n+1)*(m+1)];
    else cout<<"NO SOLUTION";
    return 0;
}


//双端队列优化
/*
很明显是一道搜索的题。

我们可以把电路板上的每个格点(横线与竖线的交叉点)看作无向图中的结点。
若两个结点x和 y是某个小方格的两个对角,则在 x与 y之间连边。
若该方格中的标准件(对角线)与x到y的线段重合,则边权为 0;若垂直相交,则边权为 1 (说明需要旋转 1 次才能连通)。
然后,我们在这个无向图中求出从左上角到右下角的最短距离,就得到了结果。

这是一个边权要么是 0 ,要么是 1的无向图。在这样的图上,我们可以通过双端队列广度搜索计算。
算法的整体框架与一般的广度优先搜索类似，只是在每个结点上沿分支扩展时稍作改变。
如果这条分支是边权为0的边，就把沿改分支到达的新节点从队头入队；
如果这条分支是边权为1的边，就像一般的广度优先搜索一样从队尾入队。
这样一来，我们就仍然能保证任意时刻广度优先搜索队列中的结点对应的距离值都具有"两段性"和“单调性”
每个结点从队头出队时，就能得到从左上角到该结点的最短距离。

因为每个结点只需要访问一次，所以算法的时间复杂度为O(n×m)。
*/
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=505;
char map[maxn][maxn];
bool used[maxn][maxn];
int dx[4]={1,1,-1,-1},
    dy[4]={1,-1,1,-1};
int n,m,dis[maxn][maxn];
deque< pair<int,int> >q,empty;
bool turn(int x1,int y1,int x2,int y2)
{
    int x=map[(x1+x2)/2][(y1+y2)/2]=='/'?1:-1;
    return x==(y1-y2)/(x1-x2);
}
void bfs()
{
    memset(used,0,sizeof(used));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    q=empty;q.push_back(make_pair(0,0));dis[0][0]=0;//清零!!!
    while(!q.empty())
    {
        int a=q.front().first,
            b=q.front().second;
        q.pop_front();used[a][b]=true;
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+a,y=dy[i]+b;
            if(x<0||n<x||y<0||m<y||used[x][y])
                continue;
            if(turn(a,b,x,y))//如果电线不直接连接两个点,即代价为1
            {//就把结点按正常入队
                dis[x][y]=min(dis[x][y],dis[a][b]+1);//注意要取最小值
                q.push_back(make_pair(x,y));
            }
            else//如果电线直连,那么到(a,b),(x,y)两个点的步数是一样的
            {//换句话说,他们的层级是一样的,由于一般的广搜的队列层级是单调递增的,所以为了保证这个性质,将(x,y)从队首入队.
                dis[x][y]=min(dis[x][y],dis[a][b]);
                q.push_front(make_pair(x,y));
            }
            if(x==n&&y==m) return;
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%s",map[i]);
        if((n+m)%2)
        {
            puts("NO SOLUTION");
            continue;
        }
        bfs();
        printf("%d\n",dis[n][m]);
    }
    return 0;
}