王子救公主 （计蒜客）一道简单DFS

　

救公主

蓝桥杯不能粘贴  只能截图。。

这道题目很简单，主要想清楚 只要存在王子和公主都能到达的点，王子就能救出公主（此时必定有一个时刻可以让他们相遇）

#include <bits/stdc++.h>
using namespace std;
const int M = 100000+100;
char mp[110][110];
int n,m,visw[110][110],visg[110][110];
void dfsw(int x,int y)
{
    if(x<=n&&x>=1&&y>=1&&y<=m&&!visw[x][y]&&mp[x][y]!='#')
    {
        visw[x][y]=1;
        dfsw(x+2,y);
        dfsw(x-2,y);
        dfsw(x,y+2);
        dfsw(x,y-2);
    }
    return ;
}
void dfsg(int x,int y)
{
    //printf("g    %d   %d\n",x,y);
    if(x<=n&&x>=1&&y>=1&&y<=m&&!visg[x][y]&&mp[x][y]!='#')
    {
        visg[x][y]=1;
        dfsg(x+1,y);
        dfsg(x-1,y);
        dfsg(x,y+1);
        dfsg(x,y-1);
    }
    return ;
}
void dfsg()
{

}
int main()
{
    int sx,sy,gx,gy,wx,wy;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%s",mp[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(mp[i][j]=='g')
                gx=i,gy=j;
            if(mp[i][j]=='w')
                wx=i,wy=j;
        }
    dfsw(wx,wy);
    dfsg(gx,gy);
    int flag=0;
    for(int i = 1;i <= n; i++)
        for(int j=1;j<=m;j++)
        {
            if(visw[i][j]==1&&visg[i][j]==1)
                flag=1;
        }
    if(flag)
        puts("yes");
    else
        puts("no");
    return 0;
}

文章最后发布于: 2019-03-21 23:05:40

相关阅读

广告系统设计：流量提升

上一篇中，二哈简单的介绍了一下广告系统的整体架构，如果掌握的话，基本就可以搭建出一个完整的广告系统啦！那么问题来了，广告系统搭出来

从Salesforce看，如何理解并设计CRM系统？

最近由于工作所需，为公司的销售团队设计了一套内部使用的CRM销售管理系统。为了设计好该类型的产品，特地去研究并分析了该领域的巨

设计师如何准备职级晋升

每次快到晋级答辩的时候，大家都会绞尽脑汁地准备PPT。相信很多参加过晋级的同学，都总结出了一套自己的方法，但仍有部分同学会感到困

数据探索平台设计——“CheckStyle”

数据工具产品很重要，但是这方面的人才却很稀缺。本篇文章作者结合自己的数据产品经验，介绍了数据探索平台设计——“CheckStyle”。

优秀的淘宝店招怎么制作？实用的设计思路分享

淘宝店招做不好会影响店铺的转化率，各位卖家是不是很想知道优秀的淘宝店招怎么制作的方法和技巧呢?seo实验室小编为大家准备了一些