題目來源: http://community.topcoder.com/stat?c=problem_statement&pm=3005&rd=5858
思路:
如果直接用Brute Force搜索所有可能的圓的話,那么搜索空間將很大,所以我用了一個priority_queue結構,將搜索的順序變?yōu)榘磮A的半徑從大到小搜索,所以當搜索到符合條件的圓時,即可停止搜索。這樣可以大大減少搜索范圍,不過對于最壞的情況,也就是沒有符合條件的圓時,還是會將所有的可能情況都搜索到。
代碼如下:
?
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <utility> #include <cmath> using namespace std; typedef pair <int, pair<int, int> > entry; #define make_entry(radius, row, col) ( make_pair( (radius), make_pair( (row), (col) ) ) ) class LargestCircle { public: int radius(vector <string> grid); }; bool checkCircle(int cusRadius, int cus_row, int cus_col, vector<string> & grid); int LargestCircle::radius(vector<string> grid) { int i, j; int rows, cols, cus_row, cus_col; priority_queue <entry> PQ; int maxRadius, cusRadius; rows = grid.size(); cols = grid[0].size(); for (i = 0; i < rows - 1; i++) { for (j = 0; j < cols - 1; j++) { PQ.push(make_pair(min(min(i + 1, j + 1), min(rows - i - 1, cols - j - 1)), make_pair(i, j))); } } maxRadius = 0; while ( !PQ.empty() ) { cusRadius = PQ.top().first; cus_row = PQ.top().second.first; cus_col = PQ.top().second.second; PQ.pop(); if ( checkCircle(cusRadius, cus_row, cus_col, grid) ) { maxRadius = cusRadius; break; } --cusRadius; if (cusRadius > 0) { PQ.push(make_entry(cusRadius, cus_row, cus_col)); } } return maxRadius; } /** * 檢查該圓是否合法 */ bool checkCircle(int cusRadius, int cus_row, int cus_col, vector<string> & grid) { int i, j; double pre_bias, next_bias; int pre_cell, next_cell; int next_row, next_col; next_bias = 0; for (i = 0; i < cusRadius; i++) { pre_bias = next_bias; /* pre_bias值與上一個循環(huán)中的 next_bias值相等 */ next_bias = sqrt( pow( (double)cusRadius, 2 ) - pow( (double)(cusRadius-i - 1), 2 ) ); pre_cell = (int)pre_bias; next_cell = (int)next_bias; if ( abs( next_bias - next_cell > 0.00001)) { ++next_cell; } for (j = 0; j < next_cell - pre_cell; j++) { next_row = cus_row - (cusRadius - i) + 1; next_col = cus_col - pre_cell - j; if ('#' == grid[next_row][next_col] || '#' == grid[next_row][2 * cus_col + 1 - next_col] || // 右對稱點 '#' == grid[2 * cus_row + 1 - next_row][next_col] || // 下對稱點 '#' == grid[2 * cus_row + 1 - next_row][2 * cus_col + 1 - next_col]) { //中心對稱 return false; } } } return true; }
?
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
