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

#include<bits/stdc++.h>
using namespace std;
#define int long long
int r,c;
int kx,ky;
int Map[1001][1001];
namespace bfs{
    const int dx[8]={1,1,2,2,-1,-1,-2,-2};
    const int dy[8]={2,-2,1,-1,2,-2,1,-1};
    int dis[1001][1001][2];
    int vis[1001][1001][2];
    struct node{
        int x,y,z;
    };
    queue < node > q;
    void init(){
        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
                dis[i][j][0]=dis[i][j][1]=2000000,
                vis[i][j][0]=vis[i][j][1]=0;
    }
    int bfs(int st1,int st2)
    {
        init();
        node st;
        if(st1==kx&&st2==ky)
            dis[st1][st2][1]=0,
            vis[st1][st2][1]=1,
            st=(node){st1,st2,1};
        else
            dis[st1][st2][0]=0,
            vis[st1][st2][0]=1,
            st=(node){st1,st2,0};
        q.push(st);
        while(!q.empty()){
            node now=q.front();
            q.pop();
            vis[now.x][now.y][now.z]=0;
            for(int i=0; i<8; i++){
                node nt=(node){
                    now.x+dx[i],
                    now.y+dy[i],
                    now.z
                };
                if(nt.x<1||nt.y<1||nt.x>r||nt.y>c)continue;
                if(dis[nt.x][nt.y][nt.z]>dis[now.x][now.y][now.z]+1){
                    dis[nt.x][nt.y][nt.z]=dis[now.x][now.y][now.z]+1;
                    if(vis[nt.x][nt.y][nt.z]==0){
                        vis[nt.x][nt.y][nt.z]=1;
                        q.push(nt);
                    }
                }
            }
            if(now.z==0){
                node nt=(node){
                    now.x,
                    now.y,
                    1
                };
                int total=max(abs(kx-nt.x),abs(ky-nt.y));
                if(dis[nt.x][nt.y][nt.z]>dis[nt.x][nt.y][nt.z^1]+total){
                    dis[nt.x][nt.y][nt.z]=dis[nt.x][nt.y][nt.z^1]+total;
                    if(vis[nt.x][nt.y][nt.z]==0){
                        vis[nt.x][nt.y][nt.z]=1;
                        q.push(nt);
                    }
                }
            }
        }
        int ans=2000000,answer=0;
        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
            if(Map[i][j]==1)
                ans=min(ans,dis[i][j][1]-dis[i][j][0]),
                answer+=dis[i][j][0];
        return ans+answer;
    }
}
signed main()
{
    //freopen("text.in","r",stdin);
    cin>>c>>r;//ÁÐÊý£¬ÐÐÊý
    char A;int B;cin>>A>>B;
    kx=A-'A'+1;
    ky=B;
    while(cin>>A>>B){
        Map[A-'A'+1][B]=1;
        //cout<<A-'A'+1<<" "<<B<<endl;
    }
    int ans=2000000;
    for(int i=1; i<=r; i++)
        for(int j=1; j<=c; j++)
        ans=min(ans,bfs::bfs(i,j));//,printf("%d ",bfs::bfs(i,j));
    //puts("");
    if(ans==2000000)cout<<0<<endl;
    else
    cout<<ans<<endl;
    return 0;
}

原文地址：http://www.cnblogs.com/dadidididi/p/16800306.html