首页 > 代码库 > HDU 1035 [Robot Motion] 模拟 记忆
HDU 1035 [Robot Motion] 模拟 记忆
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1035
题目大意：给出一个地图，每个点都指定下一步的方向。问移动情况（何时走出地图或几步后进入多长的循环）
关键思想：模拟+记忆化。我的做法是访问过的点vis置1，往后每走一步，走过的所有点vis++，因为每个点都可能是循环的节点。后面回到一个vis>1的点，vis-1就是循环长度了。（也可以记录到每个点的步数，最后点的步数差值就是循环长度）
代码如下
//模拟 记忆。可优化
#include <iostream>
#include <memory.h>
using namespace std;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int flag[13][13];//记录方向
int vis[13][13];
int N,M,S;//S为起点
void add(){
//维护可能的循环长度
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
if(vis[i][j])vis[i][j]++;
}
}
return ;
}
int main(){
int x,y,cnt;
int dx,dy;
char temp;
while(~scanf("%d%d%d",&N,&M,&S)&&N){
memset(flag,0,sizeof(flag));
memset(vis,0,sizeof(vis));
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
cin>>temp;
switch(temp){
case ‘E‘:flag[i][j]=0;break;
case ‘S‘:flag[i][j]=1;break;
case ‘W‘:flag[i][j]=2;break;
case ‘N‘:flag[i][j]=3;break;
default:break;
}
}
}
x=1,y=S,cnt=0;
while(x>=1&&x<=N&&y>=1&&y<=M&&!vis[x][y]){
vis[x][y]=true;
dx=dir[flag[x][y]][0],dy=dir[flag[x][y]][1];//不用dx,dy作为中间变量会有BUG
x+=dx,y+=dy;
cnt++;
add();
}
if(vis[x][y]>1)vis[x][y]--;
if(vis[x][y])cout<<cnt-vis[x][y]<<" step(s) before a loop of "<<vis[x][y]<<" step(s)"<<endl;
else cout<<cnt<<" step(s) to exit"<<endl;
}
return 0;
}
HDU 1035 [Robot Motion] 模拟 记忆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。