C++ 实现球迷 今日头条面试题

2020-01-06 19:17:02于海丽

6,8

其他:

对于100%的数据,1<=M,N<=3e3。

这道题是一道明显的深度优先搜索,而且十分简单。

但是在看到输入示例后会发现每个数据的后面都存在着一个字符,而且回车也属于字符。

所以我们要先对数据进行处理。

我们需要使用的的辅助工具就是getchar()了,不知道的人可以把getchar()作为一个爪子,每当一个char类型的字符被输入后,getchar()就可以准确的捕捉到他。

但是getchar()是会忽略每行第一个字符的。

所以我们可以定义一个数组,在取完第一个数后再使用getchar()。就可以把所有的0和1存储在一个n*m的二维数组中了。

再说dfs,就十分简单了,只需要判断可能走的8个方向,再使用一个计数器计数就可以了。

但是为了避免走重复的路,也是为了避免时间超限。所以我们可以定义一个bool类型的数组,记录走过的路。

同时在主函数中做写一个两层的嵌套循环,找到每个1,再进行dfs。

也要注意使用scanf和printf。