链接


图论,明显是dijkstra,$d\[i\]$数组保存第$i$个药水的最小配置价格,$cnt\[i\]$保存第$i$个药水最小配置价格的方案数,具体过程: 1. 每次找一个没有访问过的配置价格最小的药水$x$。 2. 枚举所有可以和$x$组成新药水的药水$i$并且已经访问过的节点。 3. 如果$x$和$i$组成的新药水的最小配置价格$d\[j\]

    #include<bits/stdc++.h>
    using namespace std;

    int n,m;
    int a[1509][1509];
    struct node{
        int x,y;
        bool v;
    }d[1509][1509];
    bool flag=0;

    int yc[4]={0,0,-1,1},xc[4]={1,-1,0,0};

    void dfs(int x,int y,int rx,int ry){
        if(flag) return;
        if(d[x][y].v&&(d[x][y].x!=rx||d[x][y].y!=ry)){
            flag=1;
            return;
        }
        d[x][y].x=x,d[x][y].y=y,d[x][y].v=1;
        for(int i=0;i<4;i++){
            int nx,ny;
            if(x+xc[i]==0) nx=n;
            else if(x+xc[i]==n+1) nx=1;
            else nx=x+xc[i];
            if(y+yc[i]==0) ny=m;
            else if(y+yc[i]==m+1) ny=1;
            else ny=y+yc[i];
            int nrx=rx+xc[i],nry=ry+yc[i];
            if(!a[nx][ny]&&(d[nx][ny].x!=nrx||d[nx][ny].y!=nry||!d[nx][ny].v)){
                dfs(nx,ny,nrx,nry);
            }
        }
    }

    int main(){
        node start;
        while(cin>>n>>m){
            flag=0;
            for(int i=1;i<=n;i++){
                string c;
                cin>>c;
                for(int j=1;j<=m;j++){
                    d[i][j].x=0,d[i][j].y=0,d[i][j].v=0;
                    a[i][j]=0;
                    if(c[j-1]=='#') a[i][j]=1;
                    if(c[j-1]=='S') start.x=i,start.y=j;
                }
            }
            dfs(start.x,start.y,start.x,start.y);
            if(flag) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        return 0;
    }
Last modification:March 14th, 2020 at 08:53 pm