题解：P1930 [USACO3.3] 亚瑟王的宫殿

· · 题解

博客阅读 考虑暴力。
先算出骑士从每个点到任意一点的最少步数，以及是否可以到达。再算出国王从起点到每个点的最少步数（不难证明每个点一定可以到达）。
然后枚举起点、骑士接到国王的点、哪个骑士接国王，最后把答案求最小值就好了。
但是会超时，怎么办呢？
注意到当有一个骑士和国王一开始就在同一格内时并不需要枚举上述第 2 个元素，特判一下即可。
暴力的复杂度 O(R^3\times C^3)，优化后跑得飞快，最慢的点只有 50ms。

code

//bfs1为骑士的bfs,bfs2为王的bfs，修改一下xy坐标的变化值就好
cin >> n >> m;
char c;cin >> c >> kx;
ky = c - 'A' + 1;
while(cin>>c>>x[++len]){
    y[len] = c - 'A' + 1;
    if(x[len]==kx&&y[len]==ky)type = 1;
}
len--;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        bfs1(i,j) , step1[i][j][i][j] = 0;//预处理
    }
}
bfs2(kx,ky) , step2[kx][ky] = 0;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        step1[0][0][i][j] = 0;
        for(int k=1;k<=len;k++){
            if(!fl[x[k]][y[k]][i][j]){
                step1[0][0][i][j] = -1;
                break;
            }
            step1[0][0][i][j] += step1[x[k]][y[k]][i][j];//计算每个骑士到终点的步数和
        }
    }
}
if(type){//特判优化
    for(int ex=1;ex<=n;ex++){
        for(int ey=1;ey<=m;ey++){
            if(step1[0][0][ex][ey]==-1)continue;
            ans = min(ans,step1[0][0][ex][ey]);
        }
    }
    cout << ans;
    return 0;
}
for(int ex=1;ex<=n;ex++){//暴力枚举
    for(int ey=1;ey<=m;ey++){
        int tmp = step1[0][0][ex][ey] + step2[ex][ey] , cnt = tmp;
        for(int i=1;i<=len;i++){
            if(!fl[x[i]][y[i]][ex][ey]){
                tmp = 0x3f3f3f3f;
                break;
            }
            for(int ox=1;ox<=n;ox++){
                for(int oy=1;oy<=m;oy++){
                    if(!fl[x[i]][y[i]][ox][oy])continue;
                    tmp = min(tmp,cnt-step1[x[i]][y[i]][ex][ey]+step1[x[i]][y[i]][ox][oy]+step2[ox][oy]+step1[ox][oy][ex][ey]-step2[ex][ey]);
                }
            }
        }
        ans = min(ans,tmp);
    }
}