HDU 1035 Robot Motion（dfs + 模拟）

系统管理员 2023-06-04 13:55 142阅读 0赞

### 嗯... ###

## ##

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

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

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

## AC代码： ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11406188.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/ae4749098d9a49a9a18e2cdf60ec8e26.png