题目大意：
给定一幅地图，“.”是可以走的空格子，“S”是起点，“D”是终点，“X”是不可以走的墙。问有无这样的一条路，使得从S出发到D恰好在第t秒。并且，不能停留在任何位置。
分析：
因为数据范围很小，所以我使用了爆搜，但是虽然没有TLE，但是却WA了。样例过了，调试感觉也没问题，所以为什么？？？
#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
int n
,m
,t
,sx
,sy
,ex
,ey
;
char c
[10][10];
bool f
[10][10],flag
;
inline void dfs(int x
,int y
,int tm
){
if(x
<1||x
>n
||y
<1||y
>m
||!f
[x
][y
])return;
if(tm
>t
)return;
if(x
==ex
&&y
==ey
){
if(tm
==t
)flag
=true;
return;
}else{
f
[x
][y
]=false;
dfs(x
-1,y
,tm
+1);
dfs(x
,y
-1,tm
+1);
dfs(x
+1,y
,tm
+1);
dfs(x
,y
+1,tm
+1);
}return;
}
int main(){
while(scanf("%d%d%d",&n
,&m
,&t
)){
flag
=false;
memset(f
,false,sizeof(f
));
if(n
==0&&m
==0&&t
==0)break;
for(int i
=1;i
<=n
;++i
){
scanf("%s",c
[i
]+1);
for(int j
=1;j
<=m
;++j
){
if(c
[i
][j
]=='.')f
[i
][j
]=true;
else if(c
[i
][j
]=='S')sx
=i
,sy
=j
,f
[i
][j
]=true;
else if(c
[i
][j
]=='D')ex
=i
,ey
=j
,f
[i
][j
]=true;
else f
[i
][j
]=false;
}
}
for(int i
=1;i
<=n
;++i
){
for(int j
=1;j
<=m
;++j
)printf("%c",c
[i
][j
]);
printf("\n");
}
dfs(sx
,sy
,0);
if(flag
)printf("YES\n");
else printf("NO\n");
}
return 0;
}
感谢
某巨佬
\color{red}\text{某巨佬}
某巨佬帮忙调试，对搜索稍微改了改就切了这题。虽然跑了374ms，但是问题不大~
#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
int n
,m
,t
,sx
,sy
,ex
,ey
;
char c
[10][10];
bool f
[10][10],flag
;
inline void dfs(int x
,int y
,int tm
){
if(flag
)return;
if(x
==ex
&&y
==ey
){
if(tm
==t
)flag
=true;
return;
}f
[x
][y
]=0;
if(x
-1>=1&&f
[x
-1][y
]){
f
[x
-1][y
]=0;
dfs(x
-1,y
,tm
+1);
f
[x
-1][y
]=1;
}
if(y
-1>=1&&f
[x
][y
-1]){
f
[x
][y
-1]=0;
dfs(x
,y
-1,tm
+1);
f
[x
][y
-1]=1;
}
if(x
+1<=n
&&f
[x
+1][y
]){
f
[x
+1][y
]=0;
dfs(x
+1,y
,tm
+1);
f
[x
+1][y
]=1;
}
if(y
+1<=m
&&f
[x
][y
+1]){
f
[x
][y
+1]=0;
dfs(x
,y
+1,tm
+1);
f
[x
][y
+1]=1;
}
return;
}
int main(){
while(scanf("%d%d%d",&n
,&m
,&t
)){
if(n
==0&&m
==0&&t
==0)break;
flag
=false;
memset(f
,false,sizeof(f
));
for(int i
=1;i
<=n
;++i
){
scanf("%s",c
[i
]+1);
for(int j
=1;j
<=m
;++j
){
if(c
[i
][j
]=='.')f
[i
][j
]=true;
if(c
[i
][j
]=='S')sx
=i
,sy
=j
,f
[i
][j
]=true;
if(c
[i
][j
]=='D')ex
=i
,ey
=j
,f
[i
][j
]=true;
}
}
f
[sx
][sy
]=0;
dfs(sx
,sy
,0);
if(flag
)printf("YES\n");
else printf("NO\n");
}
return 0;
}
关于奇偶剪枝：
在爆搜的“if(flag)return;”下一行加上：
if((t
-tm
)<mhd
||((t
-tm
-mhd
)&1))return;
其中——
#define mhd abs(ex-x)+abs(ey-y)
加上曼哈顿距离的奇偶剪枝之后又快了100ms左右，挺好的。 因为比较简单我就不废话了。
不知道之前为什么WA了，也许是没标记初始位置和搜索时没回溯吧。 网上还有不少高级的剪枝操作，不过我觉得水过这题就行了，想进一步提升自己的读者请自行查找吧~
F
I
N
FIN
FIN
