洛谷1126-BFS

蔚落 2021-09-30 02:56 406阅读 0赞

题目链接 [https://www.luogu.org/problemnew/show/P1126][https_www.luogu.org_problemnew_show_P1126]

1 #include<iostream>
     2 #include<cstring>
     3 #include<queue>
     4 using namespace std;
     5 bool map[51][51];
     6 int vis[51][51][5];
     7 struct node{
     8     int x,y,dir,step;
     9 };
    10 queue<node> q;
    11 node aaa;
    12 int tx,ty,f,st,x1,x2,y1,y2,n,m;
    13 int fx[4]={
        0,1,0,-1},fy[4]={
        1,0,-1,0};
    14 void bfs()
    15 {
    16     while(!q.empty()){
    17         aaa=q.front();
    18         q.pop();
    19         tx=aaa.x;
    20         ty=aaa.y;
    21         if(tx==x2&&ty==y2){
    22             cout<<aaa.step;
    23             return;
    24         }
    25         for(int j=1;j<=3;j++){
    26             tx+=fx[aaa.dir];
    27             ty+=fy[aaa.dir];
    28         if(tx<=0||ty<=0||tx>=n||ty>=m||map[tx][ty]==1)
    29             break;
    30         else if(!vis[tx][ty][aaa.dir]){
    31             vis[tx][ty][aaa.dir]=true;
    32             node cnew;
    33             cnew.x=tx;
    34             cnew.y=ty;
    35             cnew.dir=aaa.dir;
    36             cnew.step=aaa.step+1;
    37             q.push(cnew);
    38         }
    39         }
    40     node cnew;
    41     cnew.x=aaa.x;
    42     cnew.y=aaa.y;
    43     cnew.step=aaa.step+1;
    44     cnew.dir=aaa.dir-1;
    45     if(cnew.dir==-1) cnew.dir=3;//如果dir=-1的话，就相当于由东向北
    46     if(!vis[cnew.x][cnew.y][cnew.dir]){
    47         vis[cnew.x][cnew.y][cnew.dir]=true;
    48         q.push(cnew);
    49     }
    50     cnew.dir=aaa.dir+1;
    51     if(cnew.dir==4) cnew.dir=0;
    52     if(!vis[cnew.x][cnew.y][cnew.dir]){
    53         vis[cnew.x][cnew.y][cnew.dir]=true;
    54         q.push(cnew);
    55     }
    56     }
    57     cout<<"-1";
    58 }
    59 int main()
    60 {
    61     cin>>n>>m;
    62     for(int i=1;i<=n;i++){
    63         for(int j=1;j<=m;j++){
    64             bool a;
    65             cin>>a;
    66             if(a){
    67                 map[i][j]=1;
    68                 map[i-1][j]=1;
    69                 map[i-1][j-1]=1;
    70                 map[i][j-1]=1;
    71             }
    72         }
    73     }
    74     for(int i=1;i<=n;i++){
    75         map[n][i]=1;
    76         map[i][m]=1;
    77     }
    78     char fang;
    79     cin>>x1>>y1>>x2>>y2>>fang;
    80     if(fang=='E') aaa.dir=0;
    81     else if(fang=='S') aaa.dir=1;
    82     else if(fang=='W') aaa.dir=2;
    83     else aaa.dir=3;
    84     aaa.x=x1;
    85     aaa.y=y1;
    86     q.push(aaa);
    87     bfs();
    88     return 0;
    89 }

转载于:https://www.cnblogs.com/572354941hnit/p/10800604.html

[https_www.luogu.org_problemnew_show_P1126]: https://www.luogu.org/problemnew/show/P1126