主要思路:全排列,然后按输入的字符串走并且判断是否撞墙
注:这样不会TLE,全排列最多24种
Code(C++):
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=60; 4 const int S=110; 5 int dx[5]={0 , -1 , 1 , 0}; //行 6 int dy[5]={1 , 0 , 0 , -1}; //列 7 // {右, 上 , 下 ,左} 8 int s[S],t[5]; 9 char a[N][N]; 10 int n,m; 11 int sx,sy,ex,ey;//开始与结束的坐标 12 int main() { 13 int ans=0; 14 cin>>n>>m; 15 for(int i=1;i<=n;i++) { 16 for(int j=1;j<=m;j++) { 17 cin>>a[i][j]; 18 if(a[i][j]=='S') { 19 sx=i;sy=j; //记下起点 20 } 21 else if(a[i][j]=='E') {//这里可以删去,后面if(x==ex && y==ex) 改为 if(a[x][y]=='E') 22 ex=i;ey=j; //记下终点 23 } 24 } 25 } 26 string st; 27 cin>>st; 28 int l=st.size(); 29 for(int i=1;i<=l;i++) s[i]=st[i-1]-'0';//将st换为数组 30 for(int i=0;i<4;i++) t[i]=i; 31 int x,y; 32 do { 33 x=sx;y=sy;//这边别忘了,每次都要初始化 34 for(int i=1;i<=l;i++) { 35 if(x>n || y>m || x<1 || y<1) break; //出界 36 x+=dx[t[s[i]]]; 37 y+=dy[t[s[i]]]; 38 if(x==ex && y==ey) { //到达终点 39 ans++; 40 break ; 41 } 42 if(a[x][y]=='#') break;//撞墙 43 } 44 }while(next_permutation(t,t+4));//全排列函数 45 cout<<ans<<endl; 46 return 0; 47 }