solved "Surrounded Regions" on LeetCode (performance-critical, thus using iterative DFS) http://oj.leetcode.com/problems/surrounded-regions/

surron_region.cpp

class Solution {
public:
    void solve(vector< vector<char> > &board) {
        height = board.size();
        if (height == 0) return;
        width = board[0].size();
        this->board = &board;
        if (height <= 2 || width <= 2) return;
        mark = new vector< vector<bool> >(height, vector<bool>(width, false));
        // mark 'O' alive
        for (int i=0; i<height; ++i) {
            if (board[i][0] == 'O' && !(*mark)[i][0])
                exploreByDFS(i, 0);
            if (board[i][width-1] == 'O' && !(*mark)[i][width-1])
                exploreByDFS(i, width-1);
        }
        for (int i=0; i<width; ++i) {
            if (board[0][i] == 'O' && !(*mark)[0][i])
                exploreByDFS(0, i);
            if (board[height-1][i] == 'O' && !(*mark)[height-1][i])
                exploreByDFS(height-1, i);
        }

        // flip surrounded 'O'
        for (int i=1; i<height-1; ++i)
            for (int j=1; j<width-1; ++j)
                if (board[i][j] == 'O' && !(*mark)[i][j])
                    board[i][j] = 'X';

        delete mark;
    }

    void exploreByDFS(int x, int y) {
        stack< pair<int, int> > s;
        s.push(make_pair(x, y));
        while (!s.empty()) {
            int px = s.top().first,
                py = s.top().second;
            s.pop();
            (*mark)[px][py] = true;
            if (px > 0 && (*board)[px-1][py] == 'O' && !(*mark)[px-1][py])
                s.push(make_pair(px-1, py));
            if (py > 0 && (*board)[px][py-1] == 'O' && !(*mark)[px][py-1])
                s.push(make_pair(px, py-1));
            if (px < height-1 && (*board)[px+1][py] == 'O' && !(*mark)[px+1][py])
                s.push(make_pair(px+1, py));  
            if (py < width-1 && (*board)[px][py+1] == 'O' && !(*mark)[px][py+1])
                s.push(make_pair(px, py+1));                                            
        }    
    }

private:
    int width, height;
    vector< vector<char> > *board;
    vector< vector<bool> > *mark;
};