CodeForces

题目链接：http://codeforces.com/problemset/problem/589/J

题意：

　　有一个扫地机器人，它的起始点是在有代表方向的方格上，它的行动规则是：按照它起始点的代表方向移动，如果遇到家具(*)或者撞墙（越界）就往右转继续走（往右转了一次之后如果还是不能走就继续往右转，所以就是顺时针方向）。

思路：

　　可以用bfs，也可以用dfs。这里我用的是dfs去模拟机器人的移动。注意的一点是，它可能陷入循环的情况，但是计数是不会重复计数的。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 char mapp[20][20];
 5 int vis[20][20];
 6 int cycle[20][20][4];     //判断是否陷入循环
 7 int n, m, ans;
 8 //顺时针方向
 9 //这里的x并不是x坐标，而是代表行，y同理代表列
10 int dx[4] = {-1, 0, 1, 0};
11 int dy[4] = {0, 1, 0, -1};
12 
13 int check(int x, int y)
14 {
15     if(x >= 0 && x < n && y >= 0 && y < m && mapp[x][y] == '.')
16         return 1;
17     return 0;
18 }
19 
20 void dfs(int x, int y, int dir) //传递坐标和方向
21 {
22     if(cycle[x][y][dir])    //陷入循环就结束
23     {
24         return;
25     }
26     cycle[x][y][dir] = 1; //记录该点和该点时的方向，如果第二次以相同方向经过该点说明陷入了循环
27     if(!vis[x][y])
28     {
29         vis[x][y] = 1;
30         //cout << x << " " << y << endl;
31         ans++;
32     }
33     int nx = x + dx[dir];
34     int ny = y + dy[dir];
35     if(check(nx, ny))
36     {
37         dfs(nx, ny, dir);
38     }
39     else    //越界的话还是以原来的坐标进行换方向移动
40     {
41         dfs(x, y, (dir + 1) % 4);
42     }
43 }
44 int main()
45 {
46     while(cin >> n >> m)
47     {
48         memset(vis, 0, sizeof(vis));
49         memset(cycle, 0, sizeof(cycle));
50         ans = 0;
51         for(int i = 0; i < n; i++)
52             cin >> mapp[i];
53         for(int i = 0; i < n; i++)
54         {
55             for(int j = 0; j < m; j++)
56             {
57                 if(mapp[i][j] == 'U')
58                 {
59                     mapp[i][j] = '.';
60                     dfs(i, j, 0);
61                 }
62                 else if(mapp[i][j] == 'R')
63                 {
64                     mapp[i][j] = '.';
65                     dfs(i, j, 1);
66                 }
67                 else if(mapp[i][j] == 'D')
68                 {
69                     mapp[i][j] = '.';
70                     dfs(i, j, 2);
71                 }
72                 else if(mapp[i][j] == 'L')
73                 {
74                     mapp[i][j] = '.';
75                     dfs(i, j, 3);
76                 }
77             }
78         }
79         cout << ans << endl;
80     }
81     return 0;
82 }