0

leetcodeに投稿された囲まれた領域の問題を解決するアルゴリズムを考え出しました。

しかし悲しいことに、私のソリューションは最初のジャッジ入力セットでは合格できますが、2 番目の大きな入力セットでは合格できず、実行時エラーが報告されます。ただし、ラップトップでは正常に実行できます。私はこの問題に何時間も費やしましたが、まだわかりません!

以下が問題です。

「X」と「O」を含む 2D ボードが与えられた場合、「X」で囲まれたすべての領域をキャプチャします。

リージョンは、囲まれたリージョン内のすべての「O」を「X」に反転することによってキャプチャされます。

例えば、

XXXX

XOOX

XXOX

XOXX

関数を実行すると、ボードは次のようになります。

XXXX

XXXX

XXXX

XOXX

以下は私の解決策です：

class Solution {
public:
    void solve(vector<vector<char> > &board) {
      if(board.size() == 0) return;

      int row = board.size();
      set<pair<int, int> > map;

      for(int i=0; i<= row/2; i++){
         int bottom = row-i-1;
         for(int j=i; j<= bottom; j++){
            checkPoint(board, i, j, map);
            checkPoint(board, bottom, j, map);
            checkPoint(board, j, i, map);
            checkPoint(board, j, bottom, map);
         }
      }        
   }

  void mark(vector<vector<char> >& board, int row, int col, set<pair<int, int> >& map){
      if(row < 0 || row > board.size()-1 || col < 0 || col > board[0].size()-1 )
          return;

    int temp = col;
    while(temp-1 >= 0 && board[row][temp-1] == 'O' &&\
        map.find(pair<int,int>(row, temp-1)) ==   map.end()){
        map.insert(pair<int, int>(row, temp-1));
        temp -=1;
        mark(board, row, temp, map);
    }
    temp = col;
    while(temp+1 <= board[0].size()-1 && board[row][temp+1] == 'O' && \
        map.find(pair<int,int>(row, temp+1)) == map.end()){
        map.insert(pair<int, int>(row, temp+1));
        temp +=1;
        mark(board, row, temp, map);
    }
    temp = row;
    while(temp -1 >= 0 && board[temp-1][col] == 'O'&& \
         map.find(pair<int,int>(temp-1, col)) == map.end()){
        map.insert(pair<int, int>(temp-1, col));
        temp -=1;
        mark(board, temp, col, map);
    }
    temp = row;
    while(temp+1 <= board.size()-1 && board[temp+1][col] == 'O'&& \
         map.find(pair<int,int>(temp+1, col)) == map.end()){
        map.insert(pair<int, int>(temp+1, col));
        temp +=1;
        mark(board, temp, col, map);
    }          
 }

  void checkPoint(vector<vector<char> >& board, int row, int col, set<pair<int, int> >& map){
     if(board[row][col] == 'O'){
       if(row ==0 || col== 0 || row == board.size()-1 || col == board[0].size()-1 ){
           if(map.find(pair<int, int>(row, col)) == map.end()){
               map.insert(pair<int,int>(row, col));
               mark(board, row, col, map);
           }
       }else if(map.find(pair<int, int>(row, col)) == map.end()){
              board[row][col] = 'X';
      }
    }
    return;
  }

};
4

2 に答える 2

0

通常、オンライン ジャッジはデスクトップとはまったく異なる環境で実行されます。サーバーはコモディティ ハードウェアを使用するため、CPU が遅くなり、メモリが少なくなる可能性があります。コードがスレッドで実行されることを妨げるものは何もありません。さらに、使用する最適化のレベルとコンパイラを制御することはできません。

このエラーは、おそらく関数の再帰的な性質によるものmarkです。実行時エラー imho は、スタックのオーバーフロー、または完了するのに時間がかかりすぎたためにプログラムが強制終了されたことが原因のいずれかまたは両方です。

関数マークはかなり直感的ではなく、コストがかかります。まず、ボードの寸法に比例する最大深さで再帰的です。ボードに 100 万行ある場合、

mark(1000000,...)   
  mark(1000000-1,...)
    ...
      mark(1,...) 
        mark(0,...)

スタックが十分に大きくない可能性があります。

第二に、同じ行または列の各セルを必要以上に「訪問済み」( ) でマークするたびに呼び出しmap.find(pair<int,int>(x, y)) == map.end()ます。グリッドが nxn だとしましょう。mark(x,y) を呼び出すと、上記のテストは行 x と行 y のそれぞれの位置に対して n 回実行されます。つまり、マークの複雑さは O(n^2) です。一般的には、O(#row^2 + #columns^2) です。

次に、次のものがあります。

 for(int i=0; i<= row/2; i++){
     int bottom = row-i-1;
     for(int j=i; j<= bottom; j++){
        checkPoint(board, i, j, map);         <--O(n^2)
        checkPoint(board, bottom, j, map);    <--O(n^2)
        checkPoint(board, j, i, map);         <--O(n^2)
        checkPoint(board, j, bottom, map);    <--O(n^2)
     }
  }

コードの実行時間は最悪でO(n^4)、n = max(row, cols) です。

ps: マークの複雑さをどのように考え出すのですか?

mark(x,y) にboard[row][y-1] = 'O'つながる

  mark(x,y-1)
  mark(x,y-2)
  ...
  mark(x,0)

各マークで、行全体が再度テストされます。関数への n 回の呼び出しを行いますmap.find(pair<int,int>(A, B))。したがって、n^2 の複雑さです。

于 2013-07-14T00:55:12.040 に答える