CodeForces 589J Cleaner Robot
题意：一个机器人打扫卫生，URDL代表初始时机器人面对的方向上右下左。 ' . ' 代表可以打扫的， ' * ' 代表家具，如果机器人遇到家具就顺时针转90度，问机器人能打扫多少面积。
题解：记录机器人走过每个点时所面对的方向，如果走过了这个点走过的方向就不用走了，模拟机器人的行走过程即可。只记录机器人第一次走过某点时面对的方向也可以。数据范围较小，开个三维vis数组也行。
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int dx[4]= {-1,0,1,0}; int dy[4]= {0,1,0,-1}; int vis[33][33][4]; int n,m,k; char c[33][33]; int sx,sy; int sum,d; void init() { sum=1; sx=-1; sy=-1; memset(vis,0,sizeof(vis)); for(int i=0; i<n; i++) { scanf("%s",c[i]); for(int j=0; j<m; j++) { if(c[i][j]=='U') { sx=i,sy=j; d=0; } if(c[i][j]=='R') { sx=i,sy=j; d=1; } if(c[i][j]=='D') { sx=i,sy=j; d=2; } if(c[i][j]=='L') { sx=i,sy=j; d=3; } } } } void dfs(int i,int j,int d) { if(c[i][j]=='.') { sum++; c[i][j]='#'; } for(k=0;k<4;k++) { int td=(k+d)%4; int x=i+dx[td]; int y=j+dy[td]; if(x>=0&&x<n&&y>=0&&y<m&&c[x][y]!='*') //走 { if(vis[x][y][td]) return; //走过的路 vis[x][y][td]=1; dfs(x,y,td); return ;//继续往下走 不是传统的栈深搜 } } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { init(); dfs(sx,sy,d); printf("%d ",sum); } return 0; }