P1699 [USACO19OPEN] Bucket Brigade B

题目大意

给一个 \(10 × 10\) 字符串矩阵，求从 \(L\) 开始（不经过 \(R\) ）到 \(B\) 的短路径。

思路

这道题因为是求最短，所以用 \(DFS\) 比较麻烦，于是我用的是 \(BFS\) 做。遇到障碍则跳过，到终点直接退出就行了。

code

#include<iostream>
using namespace std;
struct node{int x,y,from;}c[10000009];
char mp[100][100];
int way[10000009][2];
int xx[4]={0,1,0,-1},yy[4]={1,0,-1,0},n,m,ex,ey,ans;
int same(int x,int y,int k){//判重
	ans=0;
	while(k!=-1){
		if(x==c[k].x&&y==c[k].y){return 1;}
		k=c[k].from;
		++ans;
	}	
	return 0;
}

void bfs(){
	int cl=1,op=1;
	while(cl<=op){
		for(int i=0;i<4;++i){
			int tx=c[cl].x+xx[i],ty=c[cl].y+yy[i];
			if(tx<1||ty<1||tx>10||ty>10||mp[tx][ty]=='R'||same(tx,ty,cl)) continue;
			if(tx==ex&&ty==ey){cout<<ans-1<<endl;return ;}
			c[++op].x=tx;
			c[op].y=ty;
			c[op].from=cl;
		}
		++cl;
	}
}
int main(){
	for(int i=1;i<=10;++i)
		for(int j=1;j<=10;++j){
			cin>>mp[i][j];
			if(mp[i][j]=='L'){c[1].x=i,c[1].y=j;c[1].from=-1;}
			if(mp[i][j]=='B'){ex=i,ey=j;}
		}
	bfs();
	return 0;
}