Advertisement
Guest User

Untitled

a guest
Jul 4th, 2015
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. /// Your problem was okay. I've Just replaced the dfs by bfs. dfs encounter stack overflow so you got RTE.
  2. class Solution {
  3. public:
  4.     void solve(vector<vector<char> >&board) {
  5.         int m=board.size();
  6.         if(m==0) return;
  7.         int n=board[0].size();
  8.  
  9.         for(int i=0;i<m;i++){
  10.             if(board[i][0]=='O') {
  11.                 bfs(board, i, 0);
  12.             }
  13.  
  14.             if(board[i][n-1]=='O') {
  15.                 bfs(board, i, n-1);
  16.             }
  17.         }
  18.  
  19.         for(int j=1;j<n-1;j++) {
  20.             if(board[0][j]=='O') {
  21.                 bfs(board, 0, j);
  22.             }
  23.  
  24.             if(board[m-1][j]=='O') {
  25.                 bfs(board, m-1, j);
  26.             }
  27.         }
  28.         modify(board);
  29.     }
  30.  
  31.     void bfs(vector<vector<char> >& board, int i, int j) {
  32.         if(board[i][j]=='P') return;
  33.         int m=board.size();
  34.         int n=board[0].size();
  35.         queue<pair<int,int> >Q;
  36.         Q.push(make_pair(i,j));
  37.         board[i][j]='P';
  38.         while(!Q.empty()){
  39.             pair<int,int>P=Q.front();
  40.             Q.pop();
  41.             int x=P.first,y=P.second;
  42.             if(x+1<m && board[x+1][y]=='O'){
  43.                 board[x+1][y]='P';
  44.                 Q.push(make_pair(x+1,y));
  45.             }
  46.             if(x-1>=0 && board[x-1][y]=='O'){
  47.                 board[x-1][y]='P';
  48.                 Q.push(make_pair(x-1,y));
  49.             }
  50.             if(y+1<n && board[x][y+1]=='O'){
  51.                 board[x][y+1]='P';
  52.                 Q.push(make_pair(x,y+1));
  53.             }
  54.             if(y-1>=0 && board[x][y-1]=='O'){
  55.                 board[x][y-1]='P';
  56.                 Q.push(make_pair(x,y-1));
  57.             }
  58.         }
  59.     }
  60.  
  61.     void modify(vector<vector<char> >& board) {
  62.         int m=board.size();
  63.         int n=board[0].size();
  64.         for(int i=0;i<m;i++) {
  65.             for(int j=0;j<n;j++) {
  66.                 if(board[i][j]=='P') {
  67.                     board[i][j]='O';
  68.                 } else if(board[i][j]=='O') {
  69.                     board[i][j]='X';
  70.                 }
  71.             }
  72.         }
  73.     }
  74. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement