P1649 [USACO07OCT]障碍路线Obstacle Course
bfs
直接上个bfs
注意luogu的题目和bzoj有不同（bzoj保证有解，还有输入格式不同）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define pi pair<int,int>
#define mkp make_pair
#define N 105
const int d1[]={,,,-};
const int d2[]={,,-,};
char q[]; bool dan[N][N];
int a[N][N],vis[N][N],n;
pi S,T; queue<pi> h;
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i){
for(int j=;j<=n;++j){
scanf("%s",q);
if(q[]=='A') S=mkp(i,j);
if(q[]=='B') T=mkp(i,j);
if(q[]=='x') dan[i][j]=;
}
}h.push(S);
while(!h.empty()){
pi u=h.front(); h.pop();
for(int i=;i<;++i){
int r1=u.first+d1[i],r2=u.second+d2[i];
while(!dan[r1][r2]){
if(r1>n||r1<||r2>n||r2<) break;
if(vis[r1][r2]){
r1+=d1[i];r2+=d2[i];
continue;
}
vis[r1][r2]=vis[u.first][u.second]+;
if(mkp(r1,r2)==T){
printf("%d",max(,vis[r1][r2]-));
return ;
}h.push(mkp(r1,r2));
r1+=d1[i];r2+=d2[i];
}
}
}printf("-1");
return ;
}
P1649
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define pi pair<int,int>
#define mkp make_pair
#define N 105
const int d1[]={,,,-};
const int d2[]={,,-,};
char q[N]; bool dan[N][N];
int a[N][N],vis[N][N],n;
pi S,T; queue<pi> h;
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i){
scanf("%s",q);
for(int j=;j<=n;++j){
if(q[j-]=='A') S=mkp(i,j);
if(q[j-]=='B') T=mkp(i,j);
if(q[j-]=='x') dan[i][j]=;
}
}h.push(S);
while(!h.empty()){
pi u=h.front(); h.pop();
for(int i=;i<;++i){
int r1=u.first+d1[i],r2=u.second+d2[i];
while(!dan[r1][r2]){
if(r1>n||r1<||r2>n||r2<) break;
if(vis[r1][r2]){
r1+=d1[i];r2+=d2[i];
continue;
}vis[r1][r2]=vis[u.first][u.second]+;
if(mkp(r1,r2)==T){
printf("%d",max(,vis[r1][r2]-));
return ;
}h.push(mkp(r1,r2));
r1+=d1[i];r2+=d2[i];
}
}
}
}
bzoj1644