一道DFS

楼主电话面试遇到这样一道题目，现在能想到的是用DFS同时记住matrix每种状态，但这样space complexity非常大，感觉应该有更优界，求大神们指点。

given a 3*3 matrix filling

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

)">
4 5 6
7 8 9

能想到的一个优化是不存matrix，但是用十进制的integer来表示每种状态，同时用BFS搜索。

这道题我好想在leetcode上见过来着。查了一下是利口琪琪散。

lz的简化思路workable。每次用string表示，然后每一次新建int[][]还原回来进行移动。


补充内容 (2018-4-22 05:39):
严谨一些：不完全一样，琪琪散是这个的简化版。简化了一行。

谢谢，基本思路是一样的

楼上提到了leetcode有道类似的，感觉这题暴力的话就用bst（bst用set去重应该也相当于优化了）
其实我感觉跟word ladder很像。。

主楼里给的是初始状态吗？最后要换到一种什么状态呀

这道题没有像华容道一样有一个空位吗？