记忆化搜索

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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:36
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-21 17:59
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务