[已解决]可以告诉一下孩子这题走迷宫的思路吗？谢谢大佬

狂野的小黄花

英语不太好，一直以为是按规则从（1,1）走到（n,m），但发现不符合说明，有大佬能说下这题的思路是啥嘛QAQ 拜托了

最佳答案

月排行榜 / 总排行榜

damon2009a

2020-10-25 14:16:37

因为只要没有死循环的话，是一定能走出棋盘的，所以可以暴力就去尝试，DA构成死循环，SW构成死循环，DSAW，SAWD，AWDS，WDSA构成死循环，换一种意思，因为每个格子所走到的格子是一个定值，所以一个格子不可能会走到两遍，否则就算陷入死循环。
另一种方法就是逆向思维，因为格子是不会跳格子的，所以可以先判断出哪些格子能一步直接走出棋盘（就是在棋盘边缘一圈的那些格子，如果在边上，x=1时，W直接走出；x=n时，S直接走出；y=1时，A直接走出；y=m时，D直接走出以此类推，角上的话存在两种情况可以走出），接着从整个棋盘中找到可以通往这些格子的格子，在一步步往后递推。最后就能得出格子总数

跳转到最佳答案楼层

damon2009a

因为只要没有死循环的话，是一定能走出棋盘的，所以可以暴力就去尝试，DA构成死循环，SW构成死循环，DSAW，SAWD，AWDS，WDSA构成死循环，换一种意思，因为每个格子所走到的格子是一个定值，所以一个格子不可能会走到两遍，否则就算陷入死循环。
另一种方法就是逆向思维，因为格子是不会跳格子的，所以可以先判断出哪些格子能一步直接走出棋盘（就是在棋盘边缘一圈的那些格子，如果在边上，x=1时，W直接走出；x=n时，S直接走出；y=1时，A直接走出；y=m时，D直接走出以此类推，角上的话存在两种情况可以走出），接着从整个棋盘中找到可以通往这些格子的格子，在一步步往后递推。最后就能得出格子总数

damon2009a

意思大概就是给定一个二维数组（左上角是{1,1}，右下角是{n,m}），每个单元格都可能会有（W，A，S，D四种情况）
W只能往上走
A只能往左走
S只能往下走
D只能往右走
输入第一行是这个二维数组的长与宽，然后输入这个二维数组（整个二维数组只含有四个大写字母W，A，S，D之一）
最后问的是有多少格子可以从这个格子开始走出棋盘（不一定要从角上走出，边上走出也可以，只要x<1或x>n或y<1或y>n，四种情况都算走出棋盘）
我们来看样例，
DDSD
AWAA
WASD
当从第一行的四个字母D开始往右走，直接走出棋盘，1个
从第二行第一个字母A往左走，直接走出棋盘，2个
当从第三行第一个字母W往上走到A，A再往左走走出棋盘，3个
从第三行第二个字母A往右走到W，W往上走到A，A再往左走走出棋盘，4个
从第三行第三个字母S往下，直接走出棋盘，5个
当从第三行的四个字母D开始往右走，直接走出棋盘，6个
所以输出6，
（以下不输出）可以有的是（1,4) (2,1) (3,1) (3,2) (3,3) (3,4)

damon2009a

好的就评一个最佳答案吧