向错最后一个点的蒟蒻/大佬,敲响警钟!!!
一般错最后一个点的,都是没有考虑能走回头路的
如果你错了最后一个点,那么一定是开了一个标记是否走过的VIS二维数组。
我在这里是提醒大家VIS(就是判重数组,下文简称VIS)数组的真正作用,这对你以后的敲代码有着警醒的作用。
首先我们知道,最后一个点,要走回头路的,但是,这就与我们定义的“不走回头路”的VIS数组发生了矛盾,我们到底要VIS来判断这个位置是否走过有什么意义?不如删掉算了。或许真有人能删掉然后过,但是我们先不提这个。
我们得先明白,搜索算法中的VIS数组到底是用来做什么的?是用来标记某个 位置 是否走过的吧?相信很多人都是这么认为的。其实则不然。VIS数组从来都不仅仅是用来标志一个位置是否走过,VIS数组的本质,替我们判重的是“状态”!
VIS数组判重的是状态!!!也就是说,只要状态不同,哪怕位置相同也算“没走过”!!!
因此,我们很容易就能发现,这一题的状态不仅仅是行与列,还包括第三个:血量。因此,将VIS数组设为二维数组的朋友们就要注意了,状态是三维的,数组也应该是3维的
这是最后VIS数组的模样:VIS [行] [列] [当前血量]
如果定义了正确维数的VIS数组来判重,那么最后一个点的困难也迎刃而解了。
如果我的帖子能助你A了这题,那我万分荣幸!!