如何使用BFS和DFS计算网格两坐标间的最短路径

Question

我有一本包含以下内容的词典：

grid =  {
 (6, 7): 'cheese',
 (9, 2): 'cheese',
 (0, 2): 'mouse',
 (9, 1): 'cat'
}

我的起点坐标是：（9,1），终点坐标是：（0,2）。我想使用BSF和DSF来计算使用这两种方法的最短路径，这样猫就可以在老鼠吃掉所有奶酪之前吃掉老鼠。老鼠吃奶酪的部分是使用欧几里得距离找到最近的奶酪

但我不知道如何执行BFS和DFS，以找到最好的下一步行动，我的猫移动，以捕捉老鼠

我需要改变网格的数据结构吗？我知道BFS和DFS，但我不知道如何在网格中实现它们