思路:
- 回溯法,DFS
- DFS可以想象成向水中滴入了一滴墨水,任其扩散,最后我们数一数究竟扩散了多少即可。
具体细节:
- 可以借鉴12题,需要定义访问状态,边界判定,约束条件判定
- 数可以活动的范围有两种方式,1是数访问状态数组中的true值,2是书中的方式,每次递归的过程中直接计数,然后把每个递归过程中的计数相加
重难点:
- 本题采用回溯法本质算是进行搜索和遍历,同12题一样,本质上是进行试错式的暴力搜索。
- 最后要求可以走过的格子,那么何时计数就成了需要考虑的点。有三种解决方案:1.不计数,递归遍历所有能访问的格子后,统计一下状态数组里true值的个数。2.每个递归函数返回一下自己这次递归成功访问的格子数(书中的做法)3.设置一个全局参数,递归过程中每新访问一个格子就+1计数