DFS:Red and Black(POJ 1979)

时间:2023-02-10 14:44:28

               DFS:Red and Black(POJ 1979)

                红与黑

   题目大意:一个人在一个矩形的房子里,可以走黑色区域,不可以走红色区域,从某一个点出发,他最多能走到多少个房间?

   不多说,DFS深搜即可,水题

   注意一下不要把行和列搞错就好了,我就是那样弄错过一次哈哈哈哈

   

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define MAX_N 20
 4 
 5 static int dp[MAX_N][MAX_N];
 6 static int startx;
 7 static int starty;
 8 static int ans;
 9 
10 void DFS_Search(const int, const int, const int, const int);
11 
12 int main(void)
13 {
14     int W, H, i, j;
15     while (~scanf("%d%d", &W, &H))
16     {
17         if (W == 0 && H == 0)
18             break;
19         ans = 0;//先算起点的
20         for (i = 0; i < H; i++)//Read Map
21         {
22             getchar();
23             for (j = 0; j < W; j++)
24             {
25                 scanf("%c", &dp[i][j]);
26                 if (dp[i][j] == '@'){
27                     startx = i; starty = j;
28                 }
29             }
30         }
31         DFS_Search(startx, starty, W, H);
32         printf("%d\n", ans);
33     }
34 
35     return 0;
36 }
37 
38 void DFS_Search(const int x, const int y, const int W, const int H)
39 {
40     dp[x][y] = '#';
41     ans++;
42     if (x - 1 >= 0 && dp[x - 1][y] != '#')
43         DFS_Search(x - 1, y, W, H);
44     if (x + 1 < H && dp[x + 1][y] != '#')
45         DFS_Search(x + 1, y, W, H);
46     if (y - 1 >= 0 && dp[x][y - 1] != '#')
47         DFS_Search(x, y - 1, W, H);
48     if (y + 1 < W && dp[x][y + 1] != '#')
49         DFS_Search(x, y + 1, W, H);
50 }