Educational Codeforces Round 5 - C. The Labyrinth (dfs联通块操作)

题目链接：http://codeforces.com/contest/616/problem/C

题意就是给你一个n行m列的图，让你求’*‘这个元素上下左右相连的连续的’.‘有多少(本身也算一个)，每个’*‘的结果取模10。要是为’*‘输出结果，否则输出’.‘。

这个题目就是让你求连续的'.'联通块元素个数，求完一个联通块就把这个联通块标个记号(我设了ok[][]二维数组表示这个位置的元素的联通块的标号，相连的则为同一个标号)，之后这个联通块的每个元素的ans都为f(f为联通块元素个数)，然后把这些dfs过的联通块标记为经过即可。当你求’*‘周围联通的’.‘个数的时候判断上下左右的ok[][]数组是否一样，再加ans[][]答案就好。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <set>

 using namespace std;

 const int MAXN = 1e3 + ;

 char map[MAXN][MAXN];

 int tox[] = {- ,  ,  , } , toy[] = { , - ,  , } , m , n;

 int ok[MAXN][MAXN] , f , cont[MAXN * MAXN];

 typedef pair <int , int> P;

 vector <P> v;

 bool judge(int x , int y) {

     if(map[x][y] == '.' && !ok[x][y] && x >=  && x < n && y >=  && y < m) {

         return true;

     }

     return false;

 }

 void dfs(int x , int y) {

     for(int i =  ; i <  ; i++) {

         if(judge(x + tox[i] , y  + toy[i])) {

             v.push_back(P(x + tox[i] , y + toy[i]));

             ok[x + tox[i]][y + toy[i]] = f;

             dfs(x + tox[i] , y + toy[i]);

         }

     }

 }

 int main()

 {

     f = ;

     ios::sync_with_stdio(false);

     set <int> s;

     cin >> n >> m;

     for(int i =  ; i < n ; i++) {

         cin >> map[i];

     }

     memset(ok ,  , sizeof(ok));

     memset(cont ,  , sizeof(cont));

     for(int i =  ; i < n ; i++) {

         for(int j =  ; j < m ; j++) {

             if(!ok[i][j] && map[i][j] == '.') {

                 ok[i][j] = f;

                 v.clear();

                 v.push_back(P(i , j));

                 dfs(i , j);

                 cont[f++] = v.size();

             }

         }

     }

     int temp = ;

     for(int i =  ; i < n ; i++) {

         for(int j =  ; j < m ; j++) {

             if(map[i][j] == '*') {

                 temp = ;

                 s.clear();

                 for(int k =  ; k <  ; k++) {

                     int x = tox[k] + i , y = toy[k] + j;

                     if(map[x][y] == '.' && x >=  && y >=  && y < m && x < n) {

                         s.insert(ok[x][y]);

                     }

                 }

                 set<int>::iterator it = s.begin();

                 for( ; it != s.end() ; it++) {

                     temp += cont[int(*it)];

                 }

                 cout << temp % ;

             }

             else {

                 cout << '.';

             }

         }

         cout << endl;

     }

 }

巴特西

Educational Codeforces Round 5 - C. The Labyrinth (dfs联通块操作)

最新文章

热门文章