白银莲花池

· · 题解

首先，想的是3遍BFS直接求解。

但是发现前两问很好求解，但是如果到第三个问题怎么跑出来都比答案大，

因为一个点可能被增加路径后到它下一个点，之前的路径数会被重复统计。

所以f[ax][ay]+=f[x][y]应该改为f[ax][ay]++，这样就保证每次只会多出一条新的路径。

注意细节实现，同时bfs时开inq[]数组（我的ch[]数组）记录是否在队内。

如果不加，那每个点会被访问多次，导致2个点TLE。

代码

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

#define ll long long
#define mp make_pair

const int N=35;

ll dp[N][N],dis[N][N],f[N][N];

int n,m;

int sum;

int sx,sy,tx,ty;

int vis[N][N]; 

int dx[10]={1,-1,2,-2,1,-1,2,-2},dy[10]={2,2,1,1,-2,-2,-1,-1};

bool fg=0,ch[N][N];

queue<pair<int,int> > q,q1,q2;

void bfs(){
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        ch[x][y]=0;
        q.pop();
    for(int i=0;i<=7;i++){
        int ax=x+dx[i],ay=y+dy[i];
        int sum=0;
        if(ax>n||ay>m) continue;
        if(ax<=0||ay<=0) continue;
        if(vis[ax][ay]==2) continue;
        if(dp[ax][ay]>dp[x][y]+vis[ax][ay]){
            dp[ax][ay]=dp[x][y]+vis[ax][ay];
            if(ax==tx&&ay==ty) continue;
            if(ch[ax][ay]) continue;
            q.push(mp(ax,ay));
            ch[ax][ay]=1;
        }
    }
    }
}

void bfs2(){
    while(!q1.empty()){
        int x=q1.front().first;
        int y=q1.front().second;
        ch[x][y]=0;
        q1.pop();
    for(int i=0;i<=7;i++){
        int ax=x+dx[i],ay=y+dy[i];
        int sum=0;
        if(ax>n||ay>m) continue;
        if(ax<=0||ay<=0) continue;
        if(vis[ax][ay]==2) continue;
        if(dp[ax][ay]!=dp[x][y]+vis[ax][ay]) continue;
        if(dis[x][y]+1>dis[ax][ay]) {
            continue;
        }
        dis[ax][ay]=dis[x][y]+1;
        if(ch[ax][ay]) continue;
        q1.push(mp(ax,ay));
        ch[ax][ay]=1;
//      f[ax][ay]+=f[x][y];
    }
}
}

void bfs3(){
    while(!q2.empty()){
        int x=q2.front().first;
        int y=q2.front().second;
        ch[x][y]=0;
        q2.pop();

    for(int i=0;i<=7;i++){
        int ax=x+dx[i],ay=y+dy[i];
        int sum=0;
        if(ax>n||ay>m) continue;
        if(ax<=0||ay<=0) continue;
        if(vis[ax][ay]==2) continue;
        if(dis[x][y]+1!=dis[ax][ay]) {
            continue;
        }
        if(dp[x][y]+vis[ax][ay]!=dp[ax][ay]) continue;
//      dis[ax][ay]=stp+1;
        f[ax][ay]+=f[x][y];
        if(ax==tx&&ay==ty) continue;
        if(ch[ax][ay]) continue;
        q2.push(mp(ax,ay));
        ch[ax][ay]=1;
    }
}
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int p;
            scanf("%d",&p);
            if(p==3) {
                sx=i,sy=j;
                vis[i][j]=0;
            }
            if(p==4){
                tx=i,ty=j;
                vis[i][j]=0;
            }
            if(p==1) vis[i][j]=0;
            if(p==0) vis[i][j]=1;
            if(p==2) vis[i][j]=2; 
        }
    }
    memset(dp,99,sizeof(dp));
    memset(dis,99,sizeof(dis));
    memset(ch,0,sizeof(ch));
//  cout<<dp[1][1];
    dp[sx][sy]=0;
    q.push(mp(sx,sy)); 
    bfs();
    if(dp[tx][ty]==dp[0][0]) {
        printf("-1\n");
        return 0;
    }
    else printf("%lld\n",dp[tx][ty]);
    dis[sx][sy]=0;
    memset(ch,0,sizeof(ch));
    q1.push(mp(sx,sy)); 
    bfs2();
    printf("%lld\n",dis[tx][ty]);
    f[sx][sy]=1;
    memset(ch,0,sizeof(ch));
    q2.push(mp(sx,sy));
    bfs3();
    printf("%lld\n",f[tx][ty]);
}

第二种就是在一遍bfs种直接处理答案，

考虑如果荷花数更优，直接把（x,y）的信息给(ax,ay)

如果荷花数相同，但步数更优，同上

如果两个都相同，f[ax][ay]+=f[x][y]（方案数）

代码：

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

#define ll long long
#define mp make_pair

const int N=35;

ll dp[N][N],dis[N][N],f[N][N];

int n,m;

int sum;

int sx,sy,tx,ty;

int vis[N][N]; 

int dx[10]={1,-1,2,-2,1,-1,2,-2},dy[10]={2,2,1,1,-2,-2,-1,-1};

bool fg=0,ch[N][N];

queue<pair<int,int> > q;

void bfs(int x,int y){
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        ch[x][y]=0;
        q.pop();
    for(int i=0;i<=7;i++){
        bool fg=0;
        int ax=x+dx[i],ay=y+dy[i];
        int sum=0;
        if(ax>n||ay>m) continue;
        if(ax<=0||ay<=0) continue;
        if(vis[ax][ay]==2) continue;
        if(dp[ax][ay]>dp[x][y]+vis[ax][ay]){
            dp[ax][ay]=dp[x][y]+vis[ax][ay];
            dis[ax][ay]=dis[x][y]+1;
            f[ax][ay]=f[x][y];
            if(ax==tx&&ay==ty) continue;
            fg=1;
        }
        else if(dp[ax][ay]==dp[x][y]+vis[ax][ay]&&dis[ax][ay]>dis[x][y]+1){
            dp[ax][ay]=dp[x][y]+vis[ax][ay];
            dis[ax][ay]=dis[x][y]+1;
            f[ax][ay]=f[x][y];
            if(ax==tx&&ay==ty) continue;
            fg=1;   
        }
        else if(dp[ax][ay]==dp[x][y]+vis[ax][ay]&&dis[ax][ay]==dis[x][y]+1){
            f[ax][ay]+=f[x][y];
            if(ax==tx&&ay==ty) continue;
            fg=1;
        }
        if(fg&&!ch[ax][ay]){
            q.push(mp(ax,ay));
            ch[ax][ay]=1;
        }
    } 
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int p;
            scanf("%d",&p);
            if(p==3) {
                sx=i,sy=j;
                vis[i][j]=0;
            }
            if(p==4){
                tx=i,ty=j;
                vis[i][j]=0;
            }
            if(p==1) vis[i][j]=0;
            if(p==0) vis[i][j]=1;
            if(p==2) vis[i][j]=2; 
        }
    }
    memset(dp,99,sizeof(dp));
    memset(dis,99,sizeof(dis));
//  cout<<dp[1][1];
    dp[sx][sy]=0;
    dis[sx][sy]=0;
    f[sx][sy]=1;
    q.push(mp(sx,sy));
    ch[sx][sy]=1;
    bfs(sx,sy);
    if(dp[tx][ty]==dp[0][0]) {
        printf("-1\n");
        return 0;
    }
    else printf("%lld\n",dp[tx][ty]);
    printf("%lld\n",dis[tx][ty]);
    printf("%lld\n",f[tx][ty]);
}