HDU 1312 Red and Black（经典DFS）

电玩女神 2023-06-04 13:56 4阅读 0赞

### 嗯... ###

## ##

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

### 一道很经典的dfs，设置上下左右四个方向，读入时记下起点，然后跑dfs即可...最后答案加上起点的1，无需回溯！！ ###

## ##

## AC代码： ##

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

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 
     5 using namespace std;
     6 
     7 int dir[4][2] = {
         {-1, 0}, {
         1, 0}, {
         0, -1}, {
         0, 1}};
     8 
     9 int n, m, ans;
    10 bool flag[25][25];
    11 char g[25][25];
    12 
    13 inline void dfs(int x, int y){
    14     for(int i = 0; i < 4; i++){
    15         int nx = x + dir[i][0];
    16         int ny = y + dir[i][1];
    17         if(nx <= m && ny <= n && nx > 0 && ny > 0 && !flag[nx][ny] && g[nx][ny] == '.'){
    18             ans++;
    19             flag[nx][ny] = 1;
    20             dfs(nx, ny);
    21         }
    22     }
    23 }
    24 
    25 int main(){
    26     while(~scanf("%d%d", &n, &m) && n != 0 && m != 0){
    27         int x, y;
    28         memset(flag, 0, sizeof(flag));
    29         for(int i = 1; i <= m; i++){
    30             for(int j = 1; j <= n; j++){
    31                 cin >> g[i][j];
    32                 if(g[i][j] == '@'){ x = i; y = j;}
    33             }
    34         }
    35         ans = 0;
    36         flag[x][y] = 1;
    37         dfs(x, y);
    38         printf("%d\n", ans + 1);
    39     }
    40     return 0;
    41 }
    42

AC代码

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

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