백준 14716번: 현수막

 

https://www.acmicpc.net/problem/14716

 

키워드 - DFS, FLOOD FILL

 

Source

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <math.h>
#include <memory.h>
using namespace std;

#define MAX_SIZE 100
#define INF 0x7fffffff
#define CENDL "\n"
#define ll long long

#define c_reverse(s) reverse(s.begin(), s.end())
#define c_sort(s) sort(s.begin(), s.end())
#define print_vector(v) for(int i=0; i<v.size(); i++) cout << v[i];


int n, m;
int table[250][250];
bool visited[250][250];

int dx[] = {0, 1, -1, 0, 1, -1, 1, -1};
int dy[] = {1, 0, 0, -1, 1, 1,-1, -1};


void dfs(int x, int y) {
    visited[x][y] = true;

    for (int i=0; i<8; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];

        if (ax < 0 || ay < 0 || ax >= n || ay >= m) {
            continue;
        }

        if (visited[ax][ay]) {
            continue;
        }

        if (table[ax][ay] == 1) {
            visited[ax][ay] = true;
            dfs(ax, ay);
        }
    }
}

int main() {

    cin.tie(0);
    std::ios::sync_with_stdio(false);

    cin >> n >> m;

    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> table[i][j];
        }
    }

    int sol = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {

            if (table[i][j] == 1 && !visited[i][j]) {
                sol++;
                dfs(i, j);
            }
        }
    }

    cout << sol << CENDL;

    return 0; 
}​