题目链接：http://codeforces.com/problemset/problem/589/J
题意：机器人清理房间，碰到家具（阻碍物）就不能清理，给出机器人的初位置及朝向，如果当前朝向不能再继续往前走了，机器人就会向右转，问一共能清理多少地方。
分析一开始无论如何都不懂第二组样例为什么是6而不是7，后来想明白了，当他走到（1,1）位置时方向朝上，此时它已经清扫了6块区域，这是他不能继续向前走就会向右转，变成朝右的方向后还是不能继续向前走，这是它会再次向右转，变成朝下的方向后可以继续向前走了，他就会向下走，也就是从（1,1）向（2,1）走，但是（2,1）位置他之前已经清扫过了，所以之后不会再清扫新的区域，故清扫的从区域面积为6。其实自己写的代码还是很Low的，看其他人用队列写的，感觉写起来更加快速简单易懂。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<map> #include<vector> #include<cmath> #include<set> using namespace std; typedef long long ll; const int maxn = 30000 + 5; const double eps = 0.00000000000001; int vis[15][15]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; char ch[15][15]; char chr[] = {'U', 'R', 'D','L'}; int sum; int w,h; int begx,begy; char begd; struct step { int x,y; char ch; step(){} step(int x, int y,char ch):x(x),y(y),ch(ch){} }stp[200]; bool judge(int x, int y)//判断是否出界 { return( x >= 0 && y >= 0 && x < w && y < h && ch[x][y] != '*' ); } void solve(int x, int y, char h) { for(int i = 0; i < sum; i++)//如果之前有过在相同位置相同朝向的情况，返回（之后会一直重复之前的动作，不会再清理新的地方） { if(x == stp[i].x && y == stp[i].y && h == stp[i].ch) return; } if(vis[x][y] == 0)//未清理过sum++ { stp[sum].x = x,stp[sum].y = y,stp[sum].ch = h; sum++; } vis[x][y] = 1;//标记已经走过 if(h == 'U') { for(int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i];//在此方向上继续走 if(judge(xx,yy)) { solve(xx,yy,chr[i % 4]); break; } } } else if(h == 'R') { for(int i = 1; i < 5; i++) { int xx = x + dx[i % 4], yy = y + dy[i % 4]; if(judge(xx,yy)) { solve(xx,yy,chr[i % 4]); break; } } } else if(h == 'D') { for(int i = 2; i < 6; i++) { int xx = x + dx[i % 4], yy = y + dy[i % 4]; if(judge(xx,yy)) { solve(xx,yy,chr[i % 4]); break; } } } else if(h == 'L') { for(int i = 3; i < 7; i++) { int xx = x + dx[i % 4], yy = y + dy[i % 4]; if(judge(xx,yy)) { solve(xx,yy,chr[i % 4]); break; } } } return; } int main() { while(~scanf("%d%d",&w,&h)) { sum = 0; memset(ch, 0, sizeof(ch)); memset(vis, 0, sizeof(vis)); memset(stp, 0, sizeof(stp)); for(int i = 0; i < w; i++) scanf("%s",ch[i]); int flag = 0; for(int i = 0; i < w; i++) { for(int j = 0; j < h; j++) { if(ch[i][j] == 'U' || ch[i][j] == 'R' || ch[i][j] == 'D' || ch[i][j] == 'L') { solve(i,j,ch[i][j]); begx = i, begy = j,begd = ch[i][j]; flag = 1; break; } } if(flag == 1) break; } printf("%d\n",sum); } return 0; }
