找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3994|回复: 7
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Surrounded Regions】-【刷题第一弹2014】

[复制链接]

21

主题

4

精华

481

积分

高级会员

Rank: 3Rank: 3

积分
481
发表于 10-22-2014 04:42 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 eaglesky1990 于 10-22-2014 04:45 PM 编辑

快速通道:
https://oj.leetcode.com/problems/surrounded-regions/

题目:

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X XX O O XX X O XX O X X

After running your function, the board should be:

X X X XX X X XX X X XX O X X

思路:

此题如果直接从surrouned regions入手用BFS或DFS都比较麻烦,因为不知道结果是终止于X还是边界上的O, 只有终止于X时才应该翻转O。更简单的思路是用排除法,先考虑那些没有被surrounded的O, 找他们比较简单,直接从边界上的O开始BFS或DFS遍历即可,把他们都变成'B'(啥mark都可以,只要别是'O'或'X'),然后遍历棋盘每个棋子,把遇到的'O'变成'X‘, ’B‘还原成'O'即可。

代码:

  1. void bfsBoundary(vector<vector<char> >& board, int w, int l)
  2. {
  3.     int width = board.size();
  4.     int length = board[0].size();
  5.     deque<pair<int, int> > q;
  6.     q.push_back(make_pair(w, l));
  7.     board[w][l] = 'B';
  8.     while (!q.empty()) {
  9.         pair<int, int> cur = q.front();
  10.         q.pop_front();
  11.         pair<int, int> adjs[4] = {{cur.first-1, cur.second},
  12.             {cur.first+1, cur.second},
  13.             {cur.first, cur.second-1},
  14.             {cur.first, cur.second+1}};
  15.         for (int i = 0; i < 4; ++i)
  16.         {
  17.             int adjW = adjs[i].first;
  18.             int adjL = adjs[i].second;
  19.             if ((adjW >= 0) && (adjW < width) && (adjL >= 0)
  20.                     && (adjL < length)
  21.                     && (board[adjW][adjL] == 'O')) {
  22.                 q.push_back(make_pair(adjW, adjL));
  23.                 board[adjW][adjL] = 'B';
  24.             }
  25.         }
  26.     }
  27. }

  28. void solve(vector<vector<char> > &board) {
  29.     int width = board.size();
  30.     if (width == 0) //Add this to prevent run-time error!
  31.         return;
  32.     int length = board[0].size();
  33.     if  (length == 0) // Add this to prevent run-time error!
  34.         return;

  35.     for (int i = 0; i < length; ++i)
  36.     {
  37.         if (board[0][i] == 'O')
  38.             bfsBoundary(board, 0, i);

  39.         if (board[width-1][i] == 'O')
  40.             bfsBoundary(board, width-1, i);
  41.     }

  42.     for (int i = 0; i < width; ++i)
  43.     {
  44.         if (board[i][0] == 'O')
  45.             bfsBoundary(board, i, 0);
  46.         if (board[i][length-1] == 'O')
  47.             bfsBoundary(board, i, length-1);
  48.     }

  49.     for (int i = 0; i < width; ++i)
  50.     {
  51.         for (int j = 0; j < length; ++j)
  52.         {
  53.             if (board[i][j] == 'O')
  54.                 board[i][j] = 'X';
  55.             else if (board[i][j] == 'B')
  56.                 board[i][j] = 'O';
  57.         }
  58.     }
  59.    
  60.      
  61. }
复制代码

时间复杂度: O(n) (n是棋子总数)
空间复杂度: O(n)










本帖被以下淘专辑推荐:

10

主题

1

精华

210

积分

高级会员

Rank: 3Rank: 3

积分
210
发表于 12-6-2014 05:56 AM | 显示全部楼层
这题我用java recursive做的,但是栈溢出了 求大牛指点
回复 支持 反对

使用道具 举报

0

主题

0

精华

53

积分

资深会员

Rank: 2

积分
53
发表于 12-6-2014 09:53 AM | 显示全部楼层
jiejue 发表于 12-6-2014 05:56 AM
这题我用java recursive做的,但是栈溢出了 求大牛指点

试试先从四边扫,剩下之间的白棋都是死棋了。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表