Codeforces 908B New Year and Buggy Bot 题解

主要思路:全排列,然后按输入的字符串走并且判断是否撞墙

注:这样不会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 }

 

上一篇:剑指offer62:二插搜索树的第k个节点


下一篇:python自动化