dfs_on_board.cpp

/*
 * =====================================================================================
 *
 *       Filename:  290_div2_B_fox_and_two_dots.cpp
 *
 *    Description:  290_div2_B_fox_and_two_dots.cpp
 *                  http://codeforces.com/contest/510/problem/B
 *
 *        Version:  1.0
 *        Created:  06/03/2015 12:32:31 PM
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc  
 *          email:  
 *   Organization:  
 *
 * =====================================================================================
 */

#include <iostream>
#include <utility> // for pair
#include <vector>
#include <stack>

using namespace std;

int n, m;
vector<vector<char> > board;
vector<int> dx = {0, -1, 0, 1};
vector<int> dy = {-1, 0, 1, 0};

bool has_cycle;
vector<vector<bool> > visited;

// O(|V| + |E|), same as classic DFS or BFS 
void dfsOnBoard(int x, int y, char color) {
    bool backingedge = false;
    stack<pair<pair<int, int>, pair<int, int> > > s; // parent, current
    s.push(make_pair(make_pair(-1, -1), make_pair(x, y)));
    visited[x][y] = true;
    
    while (!s.empty()) {
        pair<int, int> parent = s.top().first;
        pair<int, int> current = s.top().second;
        int next_x, next_y;
        bool found = false;
        
        for (int i = 0; i < 4 && !found; i++) {
            next_x = current.first + dx[i];
            next_y = current.second + dy[i];
            if (next_x < 0 || next_x >= n ||
                next_y < 0 || next_y >= m) {
                continue;
            }
            if (next_x == parent.first && next_y == parent.second) {
                continue;
            }
            if (board[next_x][next_y] != color) {
                continue;        
            }
            if (!visited[next_x][next_y]) { 
                found = true;
            } else { 
                if (!backingedge) {
                    has_cycle = true;
                }
            } /* if */
        } /* for */
        
        if (found) {
            s.push(make_pair(current, make_pair(next_x, next_y)));
            visited[next_x][next_y] = true;
            backingedge = false;
        } else {
            s.pop();
            backingedge = true;
        }
    } /* while */
}

int main() {
    cin >> n >> m;

    vector<char> row(m);
    for (int i = 0; i < n; i++) {
        board.push_back(row);
    }

    vector<bool> row_visited(m, false);
    for (int i = 0; i < n; i++) {
        visited.push_back(row_visited);
    }

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

    has_cycle = false;

    for (int i = 0; i < n; i++)
       for (int j = 0; j < m; j++)
          if (!visited[i][j]) 
             dfsOnBoard(i, j, board[i][j]); 

    cout << (has_cycle ? "Yes" : "No") << '\n'; 

    return 0;
}