本来以为是个大模拟，没想到自己被卡了好久…题解大佬都讲了剪枝，我自愧不如，但是个人认为本题除了剪枝这道题也有很多需要注意的细节，这篇题解我会一步一步讲自己的犯错经历，希望对你们有所帮助qwq
首先浏览一遍题意，感觉十分可做，大体思路是用dfs模拟每一次开车经历
ps:为了排版和方便阅读，只用向南作为例子，下同
pss：这篇题解不涉及剪枝内容
//v[x][y]用来记录车车的位置～
void dfs(int x,int y,int p){
//位于x，y，正在处理第p条命令
if(p>k) return ;
string heading=ord[p];
if(heading=="SOUTH"){
int fx=n-x;//对于点x,y，最多向下走n-x格
for(int i=1;i<=fx;++i){
int nx=x+i;//拓展出的点是nx,y
if(a[nx][y]=='X')//如果碰到墙，说明往后走不了了
return;
v[x][y]=false;
v[nx][y]=true;//车子从x,y开到了nx,y
dfs(nx,y,p+1);//处理下一条命令
}
}
...//三个方向
}
//a[][]是地图
int main(){
...
//输出答案
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(!v[i][j]){
if(a[i][j]=='*')
putchar('.');
else putchar(a[i][j]);
}
else putchar('*');
}
puts("");
}
return 0;
}
然后发现WA飞了hhhh（不考虑剪枝）
仔细研究样例发现，对于每个命令，不可以不做（当然），也就是说，如果车在点x,y且准备向下走，而下方紧挨着墙，则说明这种情况不存在
我们愉快的加个特判w
if(heading=="SOUTH"){
int fx=n-x;
for(int i=1;i<=fx;++i){
int nx=x+i;
if(a[nx][y]=='X'){
if(i==1)//走一步就是墙，说明车不可能在x,y
v[x][y]=false;
return;
}
v[x][y]=false;
v[nx][y]=true;
dfs(nx,y,p+1);
}
}
}过了样例，感觉自己真的很不错，提交试试
…然后又WA飞了qwq
只能下大样例…下下来也没什么思路，左思右想觉得自己很对啊，于是手玩了几个数据
5 5
X....
..X.X
.*..X
..X.X
XXX.X
5
NORTH
EAST
SOUTH
WEST
NORTH
显然答案是
X*...
**X.X
....X
..X.X
XXX.X而上面的代码跑出来了
X....
**X.X
....X
..X.X
XXX.X嗯？
经过调试发现了上面代码的本质错误…
在一次搜索中，车开到了点x,y并将其赋值为true，但是在回溯后模拟其他情况时候，又将其改为了false
orz我笨死了…
也就是这里的问题
v[x][y]=false;
v[nx][y]=true;//车子从x,y开到了nx,y,但是如果我们之前的搜索证明了x,y本身可以抵达，回溯回来时候我们又把车开走了...
dfs(nx,y,p+1);//处理下一条命令
经过几分钟思考发现了一个结论： 当且仅当执行完所有命令后，车的位置才是有效的，其他时刻都是中间量
这不是显而易见吗
于是愉快的多加一个二维数组吧
if(heading=="SOUTH"){
int fx=n-x;
for(int i=1;i<=fx;++i){
int nx=x+i;
if(a[nx][y]=='X'){
if(i==1)
v[x][y]=false;
return;
}
v[x][y]=false;
v[nx][y]=true;
if(p==k)
fin[nx][y]=true;//只有在此时才是真正的可以到达
dfs(nx,y,t+1);
}
}输出时候要按照fin的指导输出…
测了一下，终于A了滚粗…
然后回头看看代码，好像发现v数组没用上啊，开始的时候思路实在是错的彻底
精简一下代码
if(heading=="SOUTH"){
int fx=n-x;
for(int i=1;i<=fx;++i){
int nx=x+i;
if(a[nx][y]=='X') return;
if(p==k) fin[nx][y]=true;
dfs(nx,y,t+1);
}
}原来这么简单啊
总结一下，遇到题先看清题意，手玩下样例，打代码之前先模拟orzz