首页 > 代码库 > CodeForces 378C Maze (DFS)

CodeForces 378C Maze (DFS)

2024-07-23 22:29:12   218人阅读

题目链接

题意：给一个由“.”组成的联通区域，求再添加k个‘#‘以后还是联通区域的方案。

分析：做题的时候犯二了，用DFS,一直搜到边缘，然后从边缘依次往回 回溯，回溯的过程中填充’#‘

一直填充k个。

因为在搜索的过程中，一直都是vis[][]标记的，所以时间复杂度最多只是搜了所有的边，即500*500*4.

DFS搜索的时间复杂度，取决于边的个数。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <queue> 7 #include <algorithm> 8 #define LL __int64 9 const int maxn = 500+10;10 using namespace std;11 char s[maxn][maxn];12 int dx[] = {0, 0, 1, -1};13 int dy[] = {1, -1, 0, 0};14 int vis[maxn][maxn];15 int n, m, cnt;16 void dfs(int fx, int fy)17 {18     vis[fx][fy] = 1;19     for(int i = 0; i < 4; i++)20     {21         int a, b;22         a = fx+dx[i];23         b = fy+dy[i];24         if(a>=1&&a<=n && b>=1&&b<=m){}25         else continue;26         if(s[a][b]!=‘.‘) continue;27         if(!vis[a][b])28         dfs(a, b);29     }30     if(cnt)31     {32         cnt --;33         vis[fx][fy] = 2;34     }35 }36 37 int main()38 {39     int i, j;40     int fx, fy;41     while(~scanf("%d%d%d", &n, &m, &cnt))42     {43         memset(vis, 0, sizeof(vis));44         memset(s, 0, sizeof(s));45         for(i = 1; i <= n; i++)46         {47             getchar();48             for(j = 1; j <= m; j++)49             {50                 scanf("%c", &s[i][j]);51                 if(s[i][j]==‘.‘)52                 {53                     fx = i;54                     fy = j;55                 }56             }57         }58         dfs(fx, fy);59 60         for(i = 1; i <= n; i++)61         {62             for(j = 1; j <= m; j++)63                 {64                     if(vis[i][j]==2)65                     printf("X");66                     else67                     printf("%c", s[i][j]);68                 }69             printf("\n");70         }71     }72     return 0;73 }

 

CodeForces 378C Maze (DFS)


联系
我们