USACO07OCT Obstacle Course

发表于 | 分类于 |
字数统计: 633 字

题目地址

题解

暴力建图跑SPFA即可。
就是要注意建图的方式：一个点拆成4个。
同时注意输入，有坑！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
struct Edge{
    int v,cost,_next; 
}; 
Edge edge[2000005];
int cnt=0,at[40005],n,V;
int d[40005],in[40005],que[500005],f=0,r=0;
void spfa_bfs(int s){
    fill(d+1,d+4*V+1,INF);
    for(int i=0;i<4;i++)
        d[s+i*V]=0,in[s+i*V]=1,que[r++]=s+i*V;
    int i,_u,_v,_co;
    while(r-f){
        _u=que[f++],in[_u]=0;
        for(i=at[_u];i!=-1;i=edge[i]._next){
            _v=edge[i].v,_co=edge[i].cost;
            if(d[_u]+_co<d[_v]){
                d[_v]=d[_u]+_co;
                if(!in[_v]){
                    in[_v]=1,que[r++]=_v;
                }
            }
        }
    }
}
void addedge(int _u,int _v,int _cost){
    edge[cnt].v=_v,
    edge[cnt].cost=_cost,
    edge[cnt]._next=at[_u],
    at[_u]=cnt++;
} 
int xa,xb,ya,yb;
char mat[105][105];
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}	
void init(){
    n=read();
    char ord[1005];
    int tot,len;
    for(int i=1;i<=n;i++){
        fgets(ord,300,stdin);
        len=strlen(ord),tot=1;
        for(int j=0;j<len;j++)
            if(!isspace(ord[j]))mat[i][tot++]=ord[j];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(mat[i][j]=='A')xa=i,ya=j;
            else if(mat[i][j]=='B')xb=i,yb=j;
    V=n*n;
    memset(at,-1,sizeof(at));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(mat[i][j]=='x')
                continue;
            //1上2下3左4右 
            int id=(i-1)*n+j;
            addedge(id,2*V+id,1),addedge(2*V+id,id,1),
            addedge(id,V+id,2),addedge(V+id,id,2),
            addedge(id,3*V+id,1),addedge(3*V+id,id,1),
            addedge(2*V+id,V+id,1),addedge(V+id,2*V+id,1),
            addedge(3*V+id,V+id,1),addedge(V+id,3*V+id,1),
            addedge(2*V+id,3*V+id,2),addedge(3*V+id,2*V+id,2);
            if(i!=1&&mat[i-1][j]!='x')addedge(id,id-n,0);
            if(i!=n&&mat[i+1][j]!='x')addedge(V+id,V+(id+n),0);
            if(j!=1&&mat[i][j-1]!='x')addedge(2*V+id,2*V+(id-1),0);
            if(j!=n&&mat[i][j+1]!='x')addedge(3*V+id,3*V+(id+1),0);
        }
}
void solve(){
    int id=(xa-1)*n+ya;
    spfa_bfs(id);
    id=(xb-1)*n+yb;
    int ans=min(min(min(d[id],d[V+id]),d[2*V+id]),d[3*V+id]);
    printf("%d\n",ans==INF?-1:ans);
}
int main(){
    init();
    solve();
    return 0;
}