1. 机器人走网格
小红书的冒险家们!今天,我们要进入一个充满挑战的高科技迷言。这是一张由小红书科技部最新研发的网格地图,每个格子都营着秘密一它们内置了自动滑行带!这些
滑行带会让所有进入它们的机器人自动翻一个特定方向滑行。
网格地图每个格子都藏着秘密一它们内置了自动滑行带!这些滑行带会让所有进入它们的机器人自动朝一个特定方向滑行。
具体来说,一张n*m的网格地图,左上角为(1,1),右下角为(n,m),每个格子有一个滑行带,前进方向为L,R,U,D,分别表示左右上下四个方向前进。
机器人走出地图后就会毁坏,一个格子可以容纳多个机器人。
第0时刻,每个位置都有一个机器人,问:第10^8时刻,地图上还剩下多少个机器人?
有循环的会进行保留
int main() {
int n,m;
cin>>n>>m;
int dir[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
map<char,int> mp = {{'L',0},{'R',1},{'U',2},{'D',3}};
vector<vector<int>> grid(n,vector<int>(m));
vector<vector<int>> flag(n,vector<int>(m));//0表示还没有遍历过,1是循环,-1不是
char c;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>c;
grid[i][j] = mp[c];
}
}
function<bool(int,int,int)> dfs = [&](int x,int y,int id)->bool{
if(flag[x][y]>0) return true;
if(flag[x][y]==-1) return false;
int nx = x+dir[grid[x][y]][0];
int ny = y+dir[grid[x][y]][1];
if(nx<0||ny<0||nx==n||ny==m) return false;
//边界条件
flag[x][y] = id;
if(flag[nx][ny]==id)
return true;
if(dfs(nx,ny,id))
return true;
flag[x][y] = -1;
return false;
};
int res = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(dfs(i,j,i*m+j+1)) res++;
}
}
cout<<res<<endl;
return 0;
}