HDU 1035 Robot Motion（dfs + 模拟）-蒲公英云

HDU 1035 Robot Motion（dfs + 模拟）

嗯…

#

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1035

这道题比较简单，但自己一直被卡，原因就是在读入mp这张字符图的时候用了scanf被卡…

注意初始化和dfs边界：如果超出图或者曾经被标记过则输出

AC代码：

1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 
 5 using namespace std;
 6 
 7 char mp[1005][1005];
 8 int k, a, b, c, flag[1005][1005];
 9 
10 inline void dfs(int x, int y){
11     if(x <= 0 || y <= 0 || x > a || y > b){
12         printf("%d step(s) to exit\n", k);
13         return;
14     }
15     if(flag[x][y] != 0){
16         printf("%d step(s) before a loop of %d step(s)\n", flag[x][y] - 1, k - flag[x][y] + 1);//k - (flag[x][y] - 1)
17         return;
18     }
19     if(mp[x][y] == 'E'){
20         k++;
21         flag[x][y] = k;
22         dfs(x, y + 1);
23     }
24     else if(mp[x][y] == 'W'){
25         k++;
26         flag[x][y] = k;
27         dfs(x, y - 1);
28     }
29     else if(mp[x][y] == 'N'){
30         k++;
31         flag[x][y] = k;
32         dfs(x - 1, y);
33     }
34     else if(mp[x][y] == 'S'){
35         k++;
36         flag[x][y] = k;
37         dfs(x + 1, y);
38     }
39 }
40 
41 int main(){
42     while(scanf("%d%d%d", &a, &b, &c) != EOF && a + b){
43         memset(flag, 0, sizeof(flag));
44         for(int i = 1; i <= a; i++)
45             for(int j = 1; j <= b; j++)
46                 cin >> mp[i][j];//scanf会被卡 
47         k = 0;
48         dfs(1, c);
49     }
50     return 0;
51 }