sicily1702 Robot Roll Call -- Cambot...Servo...Gypsy...Croooow
这题是周赛题，当时我的想法是回溯，当然是超时，但是我还是试了，真是sb。之后就是想到把原来的图换成另外一个图。具体做法是首先把点从1～n^2编号，点（i，j）的编号为i*j。然后由于点（i， j）和它上下左右的点相连，所以i*j就和（i-1）*j，（i+1）*j，i*（j-1），i*（j+1）相连，他们的权值就是（i，j）的权值。之后用dijkstra求出最短路，再加上点（n-1，n-1）的权值就可以了。虽然说这个方法可行，但是很麻烦，超时的可能性很大，而且但是心情不好，所以我当时就没有试，后来在bbs上看到了和我思路差不多的算法，才验证了这个思路的可行性。
但是之后发现了一个更厉害的算法，就是BFS，但是该算法的提出者称之为：激情小广搜。呵呵。主要思路就是：用f[i][j]记录到（i，j）的最短路径，然后对（i，j）进行扩展的条件是找到从某个点到（i，j）这一点的新的最短路小于原来的f[i][j]。这个思路和我之前做过的广搜的不同之处就是加入了剪枝，而且不是不是纯粹的对状态进行搜索，而是对最优解答案进行搜索。从个人感觉上，有点像dp……