我寻思它也没法剪枝啊
by __Xiao__ @ 2022-10-11 14:24:42
如果同一时刻到达同一个点就只需要搜一次这个点
by Saliva_Yan @ 2022-10-11 15:01:36
@[__Xiao__](/user/727563)
```
int vis[1001][51][51];
```
```
if(vis[p][x][y])return ;
vis[p][x][y]=1;
```
把这几句加上就能A
全部代码
```
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
char a[51][51],b[51][51];
int vis[1001][51][51];
int f[3][10001];
int w[1001];//上->1,下->-1 ,左->-2,右->2
void dfs(int p,int x,int y){
if(vis[p][x][y])return ;
vis[p][x][y]=1;
if(p==q+1){
b[x][y]='*';
return ;
}
if(w[p]==1) {
for(int i=x-1;i>=1;i--){
if(a[i][y]=='X')return ;
dfs(p+1,i,y);
}
}
else if(w[p]==-1) {
for(int i=x+1;i<=n;i++){
if(a[i][y]=='X')return ;
dfs(p+1,i,y);
}
}
else if(w[p]==-2) {
for(int j=y-1;j>=1;j--){
if(a[x][j]=='X')return ;
dfs(p+1,x,j);
}
}
else if(w[p]==2){
for(int j=y+1;j<=m;j++){
if(a[x][j]=='X')return ;
dfs(p+1,x,j);
}
}
return ;
}
int main(){
cin>>n>>m;
int x,y;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='*')x=i,y=j;
}
}
cin>>q;
for(int i=1;i<=q;i++){
string s;
cin>>s;
if(s=="NORTH"){
w[i]=1;
}
else if(s=="WEST"){
w[i]=-2;
}
else if(s=="SOUTH"){
w[i]=-1;
}
else if(s=="EAST"){
w[i]=2;
}
}
f[1][0]=x;f[2][0]=y;
dfs(1,x,y);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(b[i][j]=='*')cout<<'*';
else if(a[i][j]!='*') cout<<a[i][j];
else cout<<'.';
}
cout<<"\n";
}
return 0;
}
```
by Saliva_Yan @ 2022-10-11 15:04:14
@[Saliva_Yan](/user/469784) 想通了，谢谢
by __Xiao__ @ 2022-10-11 15:12:34
@[Saliva_Yan](/user/469784) 这算增维吗
by __Xiao__ @ 2022-10-11 15:16:39
@[__Xiao__](/user/727563) zkx说不算，增维是动态规划里的东西
by Saliva_Yan @ 2022-10-11 15:18:37
@[Saliva_Yan](/user/469784) 但思想一样吧
by __Xiao__ @ 2022-10-11 15:20:30
多加一个状态
by __Xiao__ @ 2022-10-11 15:20:54
大概吧（
by Saliva_Yan @ 2022-10-11 15:22:28
@[Saliva_Yan](/user/469784)
vis数组
用bool[WA](https://www.luogu.com.cn/record/89452951)了
用int[RE](https://www.luogu.com.cn/record/89453224)了
但加上那个屁用没有的f数组就过了[AC](https://www.luogu.com.cn/record/89453489),换成bool还更快了
by __Xiao__ @ 2022-10-11 15:38:47