忍者ブログ
[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。



2017/05/01 15:17 |
PHP5.5.0 「第6回オフラインリアルタイムどう書くの参考問題」をPHPで解く
http://qiita.com/Nabetani/items/4c60f10b73812e86441c
http://nabetani.sakura.ne.jp/hena/ord6lintersection/

L字型の領域をふたつ作り、重なった部分の数を算出するという問題。
一見めんどくさそうですが、実はL字じゃなくて長方形*2とみなせば余計なこと考えなくていいので楽。
<?php

	class INTERSECTION{
		
		/**
		* 面積を返す
		* @param  String 「23-94-28,89-06-51」みたいな文字列
		* @return String 「11」みたいな文字列
		*/
		public function get($input){
			// 10*10のマップ
			$map = str_repeat('0', 100);
			
			// 入力値を分割
			$input = explode(',', $input);
			$data1 = explode('-', $input[0]);
			$data2 = explode('-', $input[1]);
			
			// マップ埋め
			$map = $this->bury($map, $data1[0], $data1[1], 1);
			$map = $this->bury($map, $data1[0], $data1[2], 1);
			$map = $this->bury($map, $data2[0], $data2[1], 2);
			$map = $this->bury($map, $data2[0], $data2[2], 2);
			
			// 重複したところをカウント
			return (string)substr_count($map, '3');
		}
		
		/**
		* 長方形内部をビット和で埋める
		* @param String マップ
		* @param String 頂点の座標
		* @param String 対角線上の頂点の座標
		* @param int 埋める値
		* @return String マップをビット和で埋めたもの
		*/
		public function bury($map, $angle1, $angle2, $val){
			for($x = min( $angle1[0], $angle2[0] );$x <= max( $angle1[0], $angle2[0] ); $x++){
				for($y = min( $angle1[1], $angle2[1] );$y <= max( $angle1[1], $angle2[1] ); $y++){
					$map[(int)$x.$y] = $map[(int)$x.$y] | $val;
				}
			}
			return $map;
		}
	}
	
	// テスト
	$test = [
		['23-94-28,89-06-51', '11'],
		/* 省略 */
	];

	$intersection = new INTERSECTION();
	foreach($test as $key=>$data){
		$answer = $intersection->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}

30分くらいで終わりました。
埋める部分の求め方がとっても力業なかんじがしますが、先日諦めたビット演算を今回はうまく使えたので満足です。

なお30分にはコメントとかは含んでいません。
ガガッと書いて30分で動いた、完成!としてから整形してJavadocとか書いてます。

それにしてもいくら読んでもこれが理解できぬ。


「オフラインリアルタイムどう書く」の一覧

PR


2013/08/12 23:59 | Comments(0) | PHP

コメント

コメントを投稿する






Vodafone絵文字 i-mode絵文字 Ezweb絵文字 (絵文字)



<<PHP5.3.3 DatePeriodのバグ? | HOME | 買ったものリスト 2013/08/11>>
忍者ブログ[PR]