CodeVS/1026

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
逃跑的拉尔夫	★☆☆☆☆	答案正确	100	2014/12/04 23:13:53	超时（30）

题意

有一些点不可以走的二维地图上，汽车能向四个方向移动，给出移动方向序列（不包括距离），求最终可能停在的点集。

题解

• 直接深搜了，没有优化T掉30分，很明显N很大，因此加个判重会优化很多，就A了。

代码

1026.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<string> #include<iostream> using namespace std; const int dirX[4]={-1,1,0,0},dirY[4]={0,0,-1,1}; int R,C,N,ii,ij,d[3000]={}; char Map[1000][1000]={}; bool dp[100][100][2000]={}; const bool inReg(const int &i,const int &j) { if(i<=0||i>R||j<=0||j>C) return 0; return 1; } void dfs(const int &i,const int &j,const int &dir) { if(dp[i][j][dir]) return; dp[i][j][dir]=1; if(dir==N+1) { Map[i][j]='*'; return; } for(int s=1;1;++s) { int newI=i+dirX[d[dir]]*s,newJ=j+dirY[d[dir]]*s; if(!inReg(newI,newJ)) return; if(Map[newI][newJ]=='X') return; dfs(newI,newJ,dir+1); } } int main() { cin>>R>>C; for(int i=1;i<=R;++i) for(int j=1;j<=C;++j) { cin>>Map[i][j]; if(Map[i][j]=='*') ii=i, ij=j, Map[i][j]='.'; } cin>>N; for(int i=1;i<=N;++i) { string p; cin>>p; if(p=="NORTH") d[i]=0; else if (p=="SOUTH") d[i]=1; else if (p=="WEST") d[i]=2; else d[i]=3; } dfs(ii,ij,1); for(int i=1;i<=R;++i) { for(int j=1;j<=C;++j) cout<<Map[i][j]; cout<<endl; } //cin>>N; }