「AOJ再挑戦66～70」の編集履歴（バックアップ）一覧に戻る

AOJ再挑戦66～70 - (2014/02/01 (土) 12:53:34) のソース

会津大学オンラインジャッジを解くページ。

*問66　Tic Tac Toe
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066
チックタックトゥの勝敗判定をする問題。

自分で考えられる限りの短縮を図ったものの平凡なショートコーディングになった。
この問題昔掲示板でヒントはもらって書いたのだけど、今回はその時より短くなっている。
短さ１位の人のコードは想像もつかないがAOJの外には１位の人より上がいるのがネットの世界。
すごいと思う。
AOJばっかりに閉じこもってないで少しは外に出ないとダメか。
コードの短さ6/542位うーん平凡。

コード解説
rはマトリックスです。
ｂに盤面データが保存されています、マス目に番号を付けると。
012
345
678

となったらチェックすべきは
012
345
678
036
147
258
048
246
の8通り。
全部　ｐ、ｐ+ｄ、ｐ+２ｄと表せます。
そしてチェックすべき３マスに入ってる文字列のビットOrをとって18でマスクをとると。
ooo＝2
か
xxx＝16
それ以外は全部18になります。
％３をとれば、ｘｘｘなら1、oooなら２、それ以外なら0を返す検出器が作れます。
あとは0を入れたｔとビットor8か所のチェックでとるだけです。



 #include<stdio.h>
 int main(){
 	char *r="0001223613432311",b[10],i,t,p,d;
  	while(scanf("%s",b)>0){
 		t=i=0;
 		while(i<8){
 			d=r[i+8]%8;
 			p=r[i++]%8;
  			t|=((b[p]|b[p+d]|b[p+d*2])&18)%3;			
 		}
 		printf("%c\n","dxo"[t]);
  	}
 }



*問67 The Number of Island
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067
格子上のデータで海と陸があらわされている島の数を数えよという問題。
解法
この問題12*1２で標準出力から読み込む問題ですが。
島と海のデータがテキストファイルで与えられデータが大きくなった場合。
たとえば数十万行*数十万列のデータでも計算できるようなアルゴリズムを構築しました。
計算量はBigO(列数*行数)です。
再帰を使った解法だと末尾最適化に成功しない限り、関数の再帰呼び出しが深くなりすぎてエラーを起こすでしょう。



 #include<stdio.h>
 #include<set>
 #include<iostream>
 const int SIZE=12;
 int main(){
 	char nowP;
 	while(1){
  		std::set<long long int> spentsNo;
 		std::set<long long int>::reverse_iterator rIt;
 		spentsNo.insert(0);
 		long long int ansAdd=0;
 		long long int oldRowMemo[SIZE]={0};
 		for(int r=0;r<SIZE;r++){
 			long long int nowRowMemo[SIZE]={0};
 			for(int c=0;c<SIZE;c++){
 				scanf("%c",&nowP);
 				if(nowP=='0'){
 					oldRowMemo[c]=nowRowMemo[c]=0;
 					continue;
 				}
 				long long int max=0;
 				if(0<c){
 					max=nowRowMemo[c-1];	
 				}
  				if(0<r){
 					max=max>oldRowMemo[c]?max:oldRowMemo[c];
 				}
 				if(max==0){
 					rIt=spentsNo.rbegin();
 					max=(*rIt)+1;
 					spentsNo.insert(max);
 				}
 				nowRowMemo[c]=max;
 				long long int t=nowRowMemo[c-1];
  				if(0<c&&t>0&&t<max){
 					spentsNo.erase(t);
 				}
 				t=oldRowMemo[c];
 				if(0<r&&t>0&&t<max){
 					spentsNo.erase(t);
 				}
 				oldRowMemo[c]=max;
 			}
 			scanf("%c",&nowP);//改行読み込み
 			//いらないデータの掃除
 			std::set<long long int> nowRowSet,dellNo;
 			for(int i=0;i<SIZE;i++){
 				nowRowSet.insert(nowRowMemo[i]);
 			}
 			for(rIt=spentsNo.rbegin();rIt!=spentsNo.rend();rIt++){
 				if(nowRowSet.find((*rIt))==nowRowSet.end()&&(*rIt)>0){
  					dellNo.insert((*rIt));
 				}
 			}
 			ansAdd+=dellNo.size();
 			for(rIt=dellNo.rbegin();rIt!=dellNo.rend();rIt++){
 				spentsNo.erase((*rIt));
			}
 		}
  		std::cout<<spentsNo.size()-1+ansAdd<<"\n";
 		if(scanf("%c",&nowP)==EOF)break;
 	}
 }