记忆化搜索

题意：一张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;
}