亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Test SRM Level Three: LargestCircle, Brute F

系統(tǒng) 1783 0

題目來源: 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;

}


  


?

?

Test SRM Level Three: LargestCircle, Brute Force


更多文章、技術交流、商務合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 欧美日韩亚洲国产一区二区综合 | 99精品国产久热在线观看66 | 九九99久久精品国产 | 国产999在线 | 高清欧美一级在线观看 | 欧美成人午夜精品一区二区 | 春色www在线视频观看 | 5x性区m免费毛片视频看看 | 日日摸夜夜爽夜夜爽出水 | 不卡视频免费在线观看 | 国产成人精品亚洲77美色 | 日韩亚洲欧美在线爱色 | 国产一区二区三区欧美 | 九九九九热精品视频 | 麻豆国产一区 | 一区二区三区久久精品 | 3d动漫免费一区二区三区 | 亚洲国产精品乱码一区二区三区 | 香蕉精品高清在线观看视频 | 天天操天天干天天干 | 久久久久欧美国产精品 | 久久爱伊人一区二区三区小说 | 伊人亚洲综合网 | 亚洲精品免费观看 | 一本岛高清v不卡免费一三区 | 国内第一永久免费福利视频 | 亚洲香蕉影院 | 九九热视频免费 | 国产美女久久久久久久久久久 | 国产欧美日韩高清专区手机版 | 日本免费毛片在线高清看 | 99久久精品费精品国产 | 国产亚洲精品久久麻豆 | 亚洲精品久久久久久久久久ty | 日本一区二区三区高清在线观看 | 精品推荐 国产 | 日本aⅴ在线 | 毛片在线网址 | 爱爱爱免费视频 | 国产亚洲精品久久久久久无 | 亚洲精品一区二 |