记忆化搜索
Walking Machine
https://ac.nowcoder.com/acm/contest/7501/I
题意:一张n*m大的地图,每个点都有一个字母,每个字母都有对应的移动规则(W : 向上 ; S : 向下 ;A:向左;D:向右),问地图中有几个点可以移到地图外去
做法:让字母对应相应的方向,因其每个点都有字母,所以每个点都只有一个可搜索的方向 记录状态(记忆化搜索)(类似洛谷的滑雪) #include<bits/stdc++.h> using namespace std; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int const N=1e3+7; int n,m,cnt; string str[N]; int xx[]={0,0,1,-1}; int yy[]={-1,1,0,0}; map<char,int>mp; int vis[N][N][2]; void dfs(int x,int y){ vis[x][y][0]=1; int dx=x+xx[ mp[ str[x][y] ] ]; int dy=y+yy[ mp[ str[x][y] ] ]; if(dx>=0&&dx<n&&dy>=0&&dy<m){ if(!vis[dx][dy][0]){ dfs(dx,dy); if(vis[dx][dy][1]==1) vis[x][y][1]=1; } else if(vis[dx][dy][1]==1){ vis[x][y][1]=1; } } else{ vis[x][y][1]=1; } } int main(){ fio; cin >> n >> m; mp['A']=0;mp['D']=1; mp['S']=2;mp['W']=3; for(int i=0;i<n;++i){ cin >> str[i]; } for(int i=0;i<n;++i){ for(int j=0;j<m;++j){ dfs(i,j); if(vis[i][j][1]==1) cnt++; } } cout << cnt; return 0; }