sjtu2018-棋盘遍历问题

题意理解:若存在一种搜索路径,使起点被遍历两次,其他所有节点被遍历一次,则返回Y

大体思路:

用isvalid数组存储每个点是否被搜索过,用sum来标志棋盘还有多少点没有被搜索。

从起点开始深度优先搜索,终止条件是搜索到起点且sum==0。若搜索到非法点或者已经遍历过的点,则剪枝。

注意回溯之后的恢复现场!

在main函数中,可以提前判断:

若棋盘面积为1,则返回Y

若行数或列数为1,则返回N


C++代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
const int N=15;
bool isvalid[N][N];
int sum;//表示棋盘总数
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

bool dfs(int x,int y)
{
    if(x==0&&y==0&&sum==0) return true;//走到起点且遍历了整个棋盘

    if(x<0||x>=n||y<0||y>=m||isvalid[x][y]) return false;//走到非法点或者该点已经遍历过


    //加入搜索路径
    isvalid[x][y]=true;
    sum--;

    //向四周搜索
    for(int i=0;i<4;i++)
    {
        int newx=x+dx[i],newy=y+dy[i];
        if(dfs(newx,newy))
            return true;

    }
    //回溯之后恢复现场
    isvalid[x][y]=false;
    sum++;

    return false;//该点加入搜索路径后不能完成任务,返回false
}




int main()
{
    while(cin>>n>>m)
    {
        memset(isvalid,0,sizeof isvalid);
        sum=n*m;

        if(sum==1)//棋盘大小为1
        {
            puts("Y");
            continue;
        }

        if(n==1||m==1&&sum!=1)//棋盘只有1行或1列
        {
            puts("N");
            continue;
        }

        if(dfs(0,0))    puts("Y");

        else puts("N");
    }

    return 0;
}


奇技淫巧: 观察可以发现

  • 若棋盘面积为1,则满足题意
  • 若棋盘行/列值不全为奇数,也可以满足题意
  • 若棋盘行/列值全为奇数,则不满足题意
  • 若棋盘为行数==1||列数==1,不满足题意

则可以得到:

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n,m;

int main()
{
    while(cin>>n>>m)
    {
        if(n*m==1) puts("Y");

        else if((n==1||m==1)&&n*m!=1) puts("N");

        else if(n%2&&m%2) puts("N");

        else puts("Y");
    }

    return 0;
}
全部评论

相关推荐

07-15 14:14
门头沟学院 Java
7.10投递7.15感谢信
投递地平线等公司7个岗位
点赞 评论 收藏
分享
Hakasee:我的简历和你的基本一样,上周去了上海,boss投了三百家, 三家线下面试 第一家没有做题,全是八股和项目,因为第一次面试不怎么熟练,挂了 第二家,给你几个题目(①css垂直居中文字,字体每两秒闪烁一下以及点击弹窗,②给你一个链接,实现可视化地图,③然后是八股,图片性能优化,以及对图片app有什么想法),45分钟内做完,然后老板面试) 第三家特别偏僻,有点阴森,到了之后让了一个工位给我,有四个题目,①格式化时间 年月日当前时间星期几② 正则表达式提取新闻文字,③在文本域输入文字生成选择题以及选项④生成商品排版还是什么来着 三家都是不超过50人的小公司 两家线上牛客笔试(卡伦特,七牛云,但是笔试不仅要考前端,还要考后端,算法,甚至数学题 我的建议是如果只做了这两个vue项目且不怎么熟练的情况下,先沉淀沉淀,把react学了,上海好的公司基本都是react查看图片
点赞 评论 收藏
分享
05-22 09:23
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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