hdoj2612 Find a way (bfs)

淡淡的烟草味﹌ 2021-12-21 01:05 158阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2612

思路：

这个题我wa了十多发QAQ。

刚开始的思路是搜索每个‘@’，然后广搜该点到Y和M的最小距离之和，最后取最小值，然后TLE了。后来换个角度，可以从Y和M分别广搜到每个‘@’的距离，这样就只用bfs两次，不用担心超时。但这个题坑点在KFC也可以当作路，Y和M也可以当作路。

AC代码如下：

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 
     4 struct node{
     5     int x,y,s;
     6 }tmp;
     7 
     8 int n,m;
     9 char a[205][205];
    10 int vis[205][205];
    11 int b[2][205][205];
    12 int go[4][2]={-1,0,0,1,1,0,0,-1};
    13 
    14 void bfs(int x,int y,int k){
    15     memset(vis,0,sizeof(vis));
    16     queue<node> q;
    17     vis[x][y]=1;
    18     tmp.x=x,tmp.y=y,tmp.s=0;
    19     q.push(tmp);
    20     while(!q.empty()){
    21         node now=q.front();q.pop();
    22         int nx=now.x,ny=now.y,ns=now.s;
    23         if(a[nx][ny]=='@')
    24             b[k][nx][ny]=ns;
    25         for(int i=0;i<4;i++){
    26             int xx=nx+go[i][0],yy=ny+go[i][1];
    27             if(xx>=0&&xx<n&&yy>=0&&yy<m&&a[xx][yy]!='#'&&!vis[xx][yy]){
    28                 vis[xx][yy]=1;
    29                 tmp.x=xx,tmp.y=yy,tmp.s=ns+1;
    30                 q.push(tmp);
    31             }
    32         }
    33     }
    34 }
    35 
    36 int main(){
    37     while(scanf("%d%d",&n,&m)!=EOF){
    38         int res=0x3f3f3f3f;
    39         for(int i=0;i<n;i++)
    40             scanf("%s",a[i]);
    41         for(int i=0;i<n;i++)
    42             for(int j=0;j<m;j++){
    43                 if(a[i][j]=='Y') bfs(i,j,0);
    44                 if(a[i][j]=='M') bfs(i,j,1);    
    45             }
    46         for(int i=0;i<n;i++)
    47             for(int j=0;j<m;j++)
    48                 if(a[i][j]=='@'&&b[0][i][j]&&b[1][i][j])
    49                     if(res>b[0][i][j]+b[1][i][j])
    50                         res=b[0][i][j]+b[1][i][j];
    51         printf("%d\n",11*res);
    52     }
    53     return 0;
    54 }

转载于:https://www.cnblogs.com/FrankChen831X/p/10356138.html