[数据结构与算法]HENAU 冬令营 搜索专题

题目链接：传送门
密码：202201110000
资料链接：
BFS算法和DFS算法（含图解：简单易懂）

题目比较经典，涉及迷宫、八皇后，全排列等题目以及变形

dfs题目

A - 棋盘问题

思路：从第一列行开始遍历，判断这一行是否可以进行放棋子，然后到下一列，注意这一行不能放是也应该到下一列
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll n,k;
char a[10][10];
bool used[10];
ll cnt=0;
/*bool judge(ll x){
    for(int i=1;i<=n;i++){

    }
}*/
void dfs(ll x,ll sum){
    if(x==n+1){
        if(sum==k){
            cnt++;
        }
        return ;
    }
    for(int i=1;i<=n;i++){
        if(a[x][i]=='.')continue;
        if(!used[i]){
            used[i]=true;
            dfs(x+1,sum+1);
            used[i]=false;
        }
    }
    dfs(x+1,sum);
    return ;
}
int main(){
    while(1){
        memset(used,false,sizeof(used));
        cin>>n>>k;
        if(n==-1&&k==-1){
            break;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>a[i][j];
            }
        }
        cnt=0;
        dfs(1,0);
        printf("%lld\n",cnt);
    }
    return 0;
}

B - Perket

思路：n<=10,数据较小，暴力求解，每一个都试试加入和不加入两种情况，取最小值
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll n;
ll s[maxn],b[maxn];
ll ans,cnt;
ll mi=1e9+10;
/*bool judge(ll x){
    for(int i=1;i<=n;i++){

    }
}*/
void dfs(ll step,ll k){
    if(step==n+1){
        if(k>=1)mi=min(mi,abs(ans-cnt));
        return ;
    }
    ans*=s[step];
    cnt+=b[step];
    dfs(step+1,k+1);
    cnt-=b[step];
    ans/=s[step];
    dfs(step+1,k);
    return ;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i]>>b[i];
    }
    ans=1;
    dfs(1,0);
    cout<<mi<<endl;
    return 0;
}

C - 全排列

思路：这是一个经典题目，下面会有一个详解，注意点是结果按字典序排列，通过对初始串进行排序解决
链接：详解
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
char str[maxn],st[maxn];
ll cnt;
ll used[maxn];
ll n;
void dfs(ll step){
    //cout<<step<<endl;
    if(step==n+1){
        for(int i=1;i<=cnt;i++){
            cout<<st[i];
        }
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!used[i]){
            used[i]=1;
            st[++cnt]=str[i];
            dfs(step+1);
            used[i]=0;
            cnt--;
        }
    }
    return ;
}
int main(){
    cin>>(str+1);
    n=strlen(str+1);
    sort(str+1,str+1+n);
    dfs(1);
    return 0;
}

D - 自然数拆分

思路：通过不断进行分层，来进行求解，每一层的初始位置从上一次分解的位置开始，可以保证所有解都可以求出，另外排除5=5，这种情况
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll n;
ll cnt;
ll a[maxn];
ll sum;
void dfs(ll x){
    //cout<<x<<endl;
    if(sum==n){
        printf("%lld=",n);
        for(int i=1;i<cnt;i++){
            printf("%lld+",a[i]);
        }
        printf("%lld\n",a[cnt]);
        return ;
    }
    if(sum>n)return ;
    for(int i=x;i<n;i++){
        sum+=i;
        cnt++;
        a[cnt]=i;
        dfs(i);
        cnt--;
        sum-=i;
    }
    return ;
}
int main(){
    cin>>n;
    dfs(1);
    return 0;
}

E - Prime Ring Problem

思路：规定第一个数为1，其余数按照全排列的方法进行即可，判断条件加上相邻两个数为素数的条件，最后输出格式需要注意一下
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll n;
ll a[maxn];
ll cnt;
ll used[maxn];
bool judge(ll x){
    if(x==1)return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}
void dfs(ll x){
    if(x==n+1){
        if(judge(a[cnt]+a[1])){
            for(int i=1;i<cnt;i++){
                printf("%lld ",a[i]);
            }
            printf("%lld\n",a[cnt]);
        }
        return ;
    }
    for(int i=2;i<=n;i++){
        if(used[i])continue;
        if(judge(a[cnt]+i)){
            used[i]=1;
            cnt++;
            a[cnt]=i;
            dfs(x+1);
            used[i]=0;
            cnt--;
        }
    }
    return ;
}
int main(){
    ll f1=0;
    while(cin>>n){
        if(f1)printf("\n");
        f1++;//对输出格式的控制
        printf("Case %lld:\n",f1);
        a[1]=1;
        cnt=1;
        dfs(2);

    }
    return 0;
}

F - Red and Black

思路：明显的迷宫搜索题目，只需要对搜索条件进行约束即可
迷宫博客链接：Dfs迷宫入门-简简单单理解dfs
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll n,m;
char a[100][100];
ll b[100][100];
ll d[2][4]={{0,1,0,-1},{1,0,-1,0}};
ll cnt=0;
void dfs(ll x,ll y){
    //cout<<x<<" "<<y<<endl;
    b[x][y]=1;
    for(int i=0;i<4;i++){
        ll dx=x+d[0][i],dy=y+d[1][i];
        //cout<<dx<<" "<<dy<<endl;
        if(dx>m||dx<1||dy>n||dy<1)continue;
        //cout<<dx<<" "<<dy<<endl;
        if(b[dx][dy])continue;
        if(a[dx][dy]=='#')continue;
        if(a[dx][dy]=='.'){
            cnt++;
            dfs(dx,dy);
        }
    }
   // b[x][y]=0;
    return ;
}
int main(){
    while(1){
        cin>>n>>m;
        if(!n&&!m){
            break;
        }
        memset(b,0,sizeof(b));
        cnt=1;
        ll sx=0,sy=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                cin>>a[i][j];
                if(a[i][j]=='@'){
                    sx=i;
                    sy=j;
                }
            }
        }
        dfs(sx,sy);
        printf("%lld\n",cnt);
    }
    return 0;
}

H - Oil Deposits

思路：本题目属于连通图题目，从一个点出发将能遍历的全部遍历一遍，有多少个出发点就有多少个联通块
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll d[2][8]={{0,1,0,-1,1,1,-1,-1},{1,0,-1,0,1,-1,1,-1}};
ll n,m;
char a[110][110];
ll b[110][110];
ll cnt;
void dfs(ll x,ll y){
    b[x][y]=1;
    for(int i=0;i<8;i++){
        ll dx=x+d[0][i];
        ll dy=y+d[1][i];
        if(dx<1||dx>n||dy<1||dy>m)continue;
        if(a[dx][dy]=='*')continue;
        if(b[dx][dy])continue;
        dfs(dx,dy);
    }
    return ;
}
int main(){
    while(1){
        cin>>n>>m;
        memset(b,0,sizeof(b));
        cnt=0;
        if(m==0&&n==0)break;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]=='*')continue;
                if(b[i][j])continue;
                dfs(i,j);
                //cout<<i<<" "<<j<<endl;
                cnt++;
            }
        }
        printf("%lld\n",cnt);
    }
    return 0;
}

I - Lake Counting

思路：上一个题目的改编题目
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll d[2][8]={{0,1,0,-1,1,1,-1,-1},{1,0,-1,0,1,-1,1,-1}};
ll n,m;
char a[110][110];
ll b[110][110];
ll cnt;
void dfs(ll x,ll y){
    b[x][y]=1;
    for(int i=0;i<8;i++){
        ll dx=x+d[0][i];
        ll dy=y+d[1][i];
        if(dx<1||dx>n||dy<1||dy>m)continue;
        if(a[dx][dy]=='.')continue;
        if(b[dx][dy])continue;
        dfs(dx,dy);
    }
    return ;
}
int main(){
    while(cin>>n>>m){

        memset(b,0,sizeof(b));
        cnt=0;
        //if(m==0&&n==0)break;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]=='.')continue;
                if(b[i][j])continue;
                dfs(i,j);
                //cout<<i<<" "<<j<<endl;
                cnt++;
            }
        }
        printf("%lld\n",cnt);
    }
    return 0;
}

J - 二叉树先序遍历

思路：只要弄清楚先序遍历的概念，就可以写，
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
//vector<ll> g[maxn];
ll n;
ll l[maxn],r[maxn];
ll cnt=0;
ll st[maxn];
void dfs(ll x){
    st[++cnt]=x;
    if(l[x]){
        dfs(l[x]);
    }
    if(r[x]){
        dfs(r[x]);
    }
    return ;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        ll x,y;
        cin>>x>>y;
        l[i]=x;
        r[i]=y;
    }
    dfs(1);
    for(int i=1;i<=cnt;i++){
        cout<<st[i]<<endl;
    }
    cout<<endl;
    return 0;
}

K - 迷宫（一）

思路：简单迷宫搜索
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
//vector<ll> g[maxn];
ll n,m;
char a[101][110];
ll d[2][4]={{0,1,0,-1},{1,0,-1,0}};
ll sx,sy;
ll cnt;
ll b[110][110];
void dfs(ll x,ll y){
    b[x][y]=1;
    if(a[x][y]=='T'){
        cnt++;
        return ;
    }
    for(int i=0;i<4;i++){
        ll dx=x+d[0][i];
        ll dy=y+d[1][i];
        if(dx<1||dx>n||dy<1||dy>m)continue;
        if(b[dx][dy])continue;
        if(a[dx][dy]=='*')continue;
        dfs(dx,dy);
    }
    return ;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='S'){
                sx=i;
                sy=j;
            }
        }
    }
    dfs(sx,sy);
    if(cnt){
        cout<<"yes";
    }else{
        cout<<"no";
    }
    return 0;
}

L - 马走日

思路：迷宫问题，改变下遍历的方向而已
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
//vector<ll> g[maxn];
ll t;
ll n,m;
ll sx,sy;
ll d[8][2]={{1,2},{1,-2},{-1,-2},{-1,2},{2,1},{2,-1},{-2,1},{-2,-1}};
ll dirx[8] = { -2,-1,1,2,2,1,-1,-2 };
ll diry[8] = { 1,2,2,1,-1,-2,-2,-1 }; //方便表示吓一跳
ll b[110][110];
ll cnt;
void dfs(ll x,ll y,ll st){
    //cout<<x<<" "<<y<<" "<<st<<endl;
    //b[x][y]=1;
    //st++;
    if(st>=n*m){
        //cout<<st<<endl;
        cnt++;
        return ;
    }
    b[x][y]=1;
    //st++;
    for(int i=0;i<8;i++){
        ll dx=x+d[i][0];
        ll dy=y+d[i][1];
        if(dx<0||dx>=n||dy<0||dy>=m)continue;
        if(b[dx][dy])continue;
        //b[dx][dy]=1;
        dfs(dx,dy,st+1);
        //b[dx][dy]=0;
    }
    //st--;
    b[x][y]=0;
    return ;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        cin>>sx>>sy;
        memset(b,0,sizeof(b));
        dfs(sx,sy,1);
        printf("%lld\n",cnt);
        cnt=0;
    }
    return 0;
}

M - 八皇后问题

思路：棋盘问题改编，多加个判断条件

ll judge(ll x,ll y){
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            if(b[i][j]){
                if((i==x)||(j==y)){
                    return 0;
                }
                if(abs(i-x)==abs(j-y))return 0;
            }
        }
    }
    return 1;
}

代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
//vector<ll> g[maxn];
ll n;
ll a[110][110],b[110][110];
ll l[110],r[110];
ll cnt;
ll ma=0;
ll judge(ll x,ll y){
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            if(b[i][j]){
                if((i==x)||(j==y)){
                    return 0;
                }
                if(abs(i-x)==abs(j-y))return 0;
            }
        }
    }
    return 1;
}
void dfs(ll step,ll s){
    if(s>=8){
        ll sum=0;
        for(int i=0;i<step;i++){
            sum+=a[l[i]][r[i]];
        }
        //cout<<sum<<endl;
        ma=max(sum,ma);
        return ;
    }
    if(step>8)return ;
    ll f=0;
    for(int i=1;i<=8;i++){
        if(judge(step,i)){
            b[step][i]=1;
            l[s]=step;
            r[s]=i;
            dfs(step+1,s+1);
            b[step][i]=0;
        }
    }
    dfs(step+1,s);
    return ;
}
int main(){
    cin>>n;
    while(n--){
        for(int i=1;i<=8;i++){
            for(int j=1;j<=8;j++){
                cin>>a[i][j];
            }
        }
        dfs(1,0);
        cout<<ma<<endl;
        ma=0;
        memset(b,0,sizeof(b));
    }
    return 0;
}

N - 选数

思路：全排列问题改变，每次从出发点往后选择数据，确保种类不重复，即避免出现结果编号重复
代码:

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll n,m;
ll a[110];
ll b[110];
ll cnt;
bool judge(ll x){
    if(x==1)return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}
void dfs(ll step,ll sum,ll s){
    if(s==m){
        if(judge(sum)){
            cnt++;
            /*for(int i=1;i<=n;i++){
                if(b[i]){
                    cout<<i<<" ";
                }
            }
            cout<<endl;*/
            //cout<<sum<<endl;
        }
    }
    if(step>n)return ;
    for(int i=step+1;i<=n;i++){//防止重复
        if(b[i])continue;
        //sum+=a[i];
        b[i]=1;
        dfs(i,sum+a[i],s+1);
        b[i]=0;
    }
    return ;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(0,0,0);
    printf("%lld\n",cnt);
    return 0;
}

bfs题目

G - Knight Moves

思路：搜索题目，单向bfs搜索超时，所以用双向的，用bfs的原因是求最短路径且数据较大
双向bfs：
单向BFS只从起点一端开始搜索，双向BFS则是从起点和终点两边扩展节点，当节点发生重合时即找到最优解。

假设起点到终点深度为d，每个节点平均有n个分支，那么单向BFS需要扩展的节点个数为。而从起点终点同时扩展，则只需。

实现方法为：维护两个队列，分别保存从起点和终点扩展到的下一层，这样保证了两个队列中的节点处于相同的深度（即：距离起点或者终点深度相同）。则当拓展到时一定发生重合，得到最优解。
代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=200100;
const int INF=pow(2,31)-1;
const int maxm=5e4+5;
const int mod=1000000007;
ll t,n;
ll dirx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
ll diry[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
ll dist1[1010][1010],dist2[1010][1010];
struct node{
    ll x;
    ll y;
}st,en;
ll judge(ll x,ll y){
    if(x<0||x>=n||y<0||y>=n){
        return 0;
    }
    return 1;
}
void bfs(){
    queue<node> p,q;
    p.push(st);
    dist1[st.x][st.y]=0;
    q.push(en);
    dist2[en.x][en.y]=0;
    while(!q.empty()&&!p.empty()){
        ll s=p.size();
        node t,tt;
        //cout<<s<<endl;
        while(s--){
            t=p.front();
            p.pop();
            if(judge(t.x,t.y)&&dist2[t.x][t.y]!=-1){
                printf("%lld\n",dist1[t.x][t.y] + dist2[t.x][t.y]);//p走到t,q走到t
                return ;
            }
            for(int i=0;i<8;i++){
                tt.x=t.x+dirx[i];
                tt.y=t.y+diry[i];
                //cout<<tt.x<<" "<<tt.y<<" "<<judge(tt.x,tt.y)<<endl;
                if(judge(tt.x,tt.y)){
                    if(dist2[tt.x][tt.y]!=-1){
                        printf("%lld\n",dist1[t.x][t.y] + dist2[tt.x][tt.y]+1);//p走到t,q走到tt
                        return ;
                    }
                    if(dist1[tt.x][tt.y]==-1){
                       // cout<<tt.x<<" "<<tt.y<<" "<<judge(tt.x,tt.y)<<endl;
                        dist1[tt.x][tt.y]=dist1[t.x][t.y]+1;
                        p.push(tt);
                    }
                }
            }
        }
        //cout<<p.size()<<" "<<q.size()<<endl;
        s=q.size();
        while(s--){
            t=q.front();
            q.pop();
            if(judge(t.x,t.y)&&dist1[t.x][t.y]!=-1){
                    printf("%lld\n",dist1[t.x][t.y] + dist2[t.x][t.y]);//p走到t,q走到t
                    return ;
            }
            for(int i=0;i<8;i++){
                tt.x=t.x+dirx[i];
                tt.y=t.y+diry[i];
                if(judge(tt.x,tt.y)){
                    if(dist1[tt.x][tt.y]!=-1){
                        printf("%lld\n",dist2[t.x][t.y] + dist1[tt.x][tt.y]+1);//p走到tt,q走到t
                        return ;
                    }
                    if(dist2[tt.x][tt.y]==-1){
                        dist2[tt.x][tt.y]=dist2[t.x][t.y]+1;
                        q.push(tt);
                    }
                }
            }
        }
        //cout<<p.size()<<" "<<q.size()<<endl;
    }

}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        cin>>st.x>>st.y;
        cin>>en.x>>en.y;
        memset(dist1,-1,sizeof(dist1));
        memset(dist2,-1,sizeof(dist2));
        bfs();
    }
    return 0;
}

O - 打开灯泡 Switch the Lamp On

思路：最短路径策略，将二维表格离散化，可以到达的点进行连接，构成无向图，将原本达到的边代价设为0，反转90度之后的边代价设为1，找最短路径即可。
最短路算法学习资料：最短路径之Dijkstra算法
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100100;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll n,m;
char a[510][510];
ll cnt[510][510];
ll tot;
ll d[510*510];
ll  vis[510*510];
struct node{
    ll to;
    ll w;
};
vector<node> g[510*510];
void dij(){
    priority_queue<P,vector<P>,greater<P> > que;
    for(int i=0;i<=tot+10;i++) d[i]=inf;
    ll s=1;
    d[s]=0;
    que.push({d[s],s});
    while(!que.empty()){
        P p=que.top();
        que.pop();
        ll u=p.second;
        //cout<<u<<endl;
        //ll v=p.first;
        if(p.first>d[u])continue;
        //vis[u]=1;
        for(int i=0;i<g[u].size();i++){
            node e=g[u][i];
            //cout<<e.to<<" ";
            if(d[e.to]>d[u]+e.w){
                d[e.to]=d[u]+e.w;
                que.push({d[e.to],e.to});
                //cout<<e.to<<endl;
            }

        }
        //cout<<endl;
    }
    if(d[tot]==inf){
        cout<<"NO SOLUTION";
    }else{
        cout<<d[tot];
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=m+1;j++){
            cnt[i][j]=++tot;
        }
    }//离散化
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='\\'){//无向图
                g[cnt[i][j]].push_back({cnt[i+1][j+1],0});
                g[cnt[i+1][j+1]].push_back({cnt[i][j],0});
                g[cnt[i][j+1]].push_back({cnt[i+1][j],1});//旋转90度
                g[cnt[i+1][j]].push_back({cnt[i][j+1],1});
            }else{
                g[cnt[i][j]].push_back({cnt[i+1][j+1],1});
                g[cnt[i+1][j+1]].push_back({cnt[i][j],1});
                g[cnt[i][j+1]].push_back({cnt[i+1][j],0});//旋转90度
                g[cnt[i+1][j]].push_back({cnt[i][j+1],0});
            }
        }
    }
    dij();
    return 0;
}