C++试题求解，急！！！！ 255
展开全部
我只想一想题解，具体写就算啦……
蒟蒻一只如果不幸搞错题解惹怒神犇勿喷=w=
首先审题发现步数显然是固定的，一个n*n的矩阵我们要走(n-1)*2步，然后我们经由左下-右上对角线把它划分为2个部分，对角线上的数字显然不用去管它因为你走的路是(n-1)个字符+中间字符+(n-1)个字符，对角线上的就是那个中间字符。
然后我们就可以愉快地开始bfs啦！
从(1,1)和(n,n)开始，分别向各自的小块开始bfs(就是把整张图变成一个上半个三角形和下半个三角形的图)，走到一个格子把那个格子里的hash表里的元素增加相应的你这次走过的路径的hash值(这里需要开对应的数组来存，比如设ABChash值是k，那么你就把hash[1][3][k]++，当然需要离散化一下)。用来记录前面走过的格子(字符串hash会吧=w=)，然后就类似折半搜索(自己取的名字，不是二分)，两边走到中间格子的hash表的东西比一比，比如样例里D那个格子从(1,1)出发就有1种ABCD，2种ABED；从(n,n)出发也有1种ABCD，2种ABED；所以D这个格子的贡献就是1*1+2*2=5
应该就是这种做法。别忘了采纳哦=w=
蒟蒻一只如果不幸搞错题解惹怒神犇勿喷=w=
首先审题发现步数显然是固定的，一个n*n的矩阵我们要走(n-1)*2步，然后我们经由左下-右上对角线把它划分为2个部分，对角线上的数字显然不用去管它因为你走的路是(n-1)个字符+中间字符+(n-1)个字符，对角线上的就是那个中间字符。
然后我们就可以愉快地开始bfs啦！
从(1,1)和(n,n)开始，分别向各自的小块开始bfs(就是把整张图变成一个上半个三角形和下半个三角形的图)，走到一个格子把那个格子里的hash表里的元素增加相应的你这次走过的路径的hash值(这里需要开对应的数组来存，比如设ABChash值是k，那么你就把hash[1][3][k]++，当然需要离散化一下)。用来记录前面走过的格子(字符串hash会吧=w=)，然后就类似折半搜索(自己取的名字，不是二分)，两边走到中间格子的hash表的东西比一比，比如样例里D那个格子从(1,1)出发就有1种ABCD，2种ABED；从(n,n)出发也有1种ABCD，2种ABED；所以D这个格子的贡献就是1*1+2*2=5
应该就是这种做法。别忘了采纳哦=w=
本回答由网友推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
