深圳哪家网站建设好,晋城网站开发,天津网站建设58,建设高校图书馆网站的意义样例输入#xff1a;
3
.xA
...
Bx.样例输出#xff1a;
6思路分析#xff1a;
这道题只需要在正常的广搜模板上多维护一个— —方向#xff0c;如果当前改变方向#xff0c;就坐标不变#xff0c;方向变#xff0c;步数加一#xff1b;否则坐标变#xff0c;方向不…
样例输入
3
.xA
...
Bx.样例输出
6思路分析
这道题只需要在正常的广搜模板上多维护一个— —方向如果当前改变方向就坐标不变方向变步数加一否则坐标变方向不变步数加一。
#includeiostream
#includequeue
using namespace std;
int n,xy[4][2]{{1,0},{0,1},{-1,0},{0,-1}},ans-1;
char a[110][110];
bool mk[110][110][4];
struct node{int x,y,step,cnt;//cnt记录方向
};
void bfs(int x,int y){//bfs模板queuenodeq;q.push((node){x,y,0,-1});//起点方向标记-1while(q.size()){node tq.front();if(a[t.x][t.y]B){//判断是否到终点anst.step;return;}q.pop();for(int i0;i4;i){int xxt.xxy[i][0],yyt.yxy[i][1];//偏移量if(xx1xxnyy1yyna[xx][yy]!xmk[xx][yy][i]0){//判断越界等if(t.cnt-1||t.cnti){//特判-1和方向不变mk[xx][yy][i]1;q.push((node){xx,yy,t.step1,i});}else{//方向改变q.push((node){t.x,t.y,t.step1,i});}}}}
}
int main(){cinn;int x,y;for(int i1;in;i){for(int j1;jn;j){cina[i][j];if(a[i][j]A){xi,yj;}}}bfs(x,y);coutans;return 0;
}
