小A与小B 搜索

小A与小B

https://ac.nowcoder.com/acm/problem/23486

题意:就是一个人走八个方向,每次走一步,一个人走四个方向,每次走2步,问最少基几步两个人相遇。
题解:首先我们要考虑好走两步的如何走,我们不能简单的把他弄成每一次直接就走2步,比如,...#D,这样子的话如果你走2步他直接就跳过障碍物了,但是实际上是走不通的,我们就可以把他处理一下,把两部变成走两次不就好啦,进行2次bfs,然后就可以解决啦,然后再同时进行另一个人的BFS,那么我们就判断他们在哪儿相遇就好啦。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
#define fro for
#define it int
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,1,0,-1,-1,1,1,-1};
   int n,m;
struct node
{
    int x,y;
}q;
queue<node>ss[2];
bool flag;
//ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
//inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
char ans[1010][1010];
int vis[1010][1010][2];
bool bfs(int a)
{
  int s=ss[a].size();
  while(s--)
  {
      node p=ss[a].front();
      ss[a].pop();
      for(int i=0;i<4+(a?0:4);i++)
      {
          int xx=p.x+dx[i];
          int yy=p.y+dy[i];
          if(xx<1||xx>n||yy<1||yy>m||ans[xx][yy]=='#'||vis[xx][yy][a]) continue;
          if(vis[xx][yy][!a]) return flag=true;
          vis[xx][yy][a]=1;
          node e;
          e=node{xx,yy};
          ss[a].push(e);
      }
  }
   return flag=false;
}
int main()
{
    int xa,ya,xb,yb;
   cin>>n>>m;
     for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=m;j++)
         {
             cin>>ans[i][j];
             if(ans[i][j]=='C')
                xa=i,ya=j;
                if(ans[i][j]=='D')
                    xb=i,yb=j;
         }
     }
    // cout<<xa<<" "<<ya<<endl;
     q=node{xa,ya},ss[0].push(q);
     q=node{xb,yb},ss[1].push(q);
     int sum=0;
     while(ss[0].size()||ss[1].size())
     {
         sum++;
         if(bfs(1)) break;
         if(bfs(1)) break;
         if(bfs(0)) break;
     }
     if(flag)
        cout<<"YES"<<"\n"<<sum<<endl;
     else
        puts("NO");
    return 0;
}
全部评论

相关推荐

找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务