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

AOJ再挑戦66～70 - (2014/01/31 (金) 05:10:04) のソース

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

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

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


 #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
格子上のデータで海と陸があらわされている島の数を数えよという問題。
解法
この問題12*1２で標準出力から読み込む問題ですが。
島と海のデータがファイルで与えられる場合、ファイルから読み込むようにすれば。
ファイルサイズが10万行*10万列とかで島のサイズが数万*数万とかになっても。
intを６４ビット整数型にしておけばスタックオーバーフローしないような計算法で解いてみました。
計算量はBigO(行サイズ*列サイズ)
再帰だと末尾再帰を実現できない限りマップサイズが大きな場合は解けません。


 #include<stdio.h>
 #include<set>
 
 const int SIZE=12;
 int main(){
 	char nowP;
 	while(1){
 		std::set<int> spentsNo;
 		std::set<int>::reverse_iterator rIt;
 		spentsNo.insert(0);
 		int oldRowMemo[SIZE]={0};
 		for(int r=0;r<SIZE;r++){
 			int nowRowMemo[SIZE]={0};
 			for(int c=0;c<SIZE;c++){
 				scanf("%c",&nowP);
 				if(nowP=='0'){
 					oldRowMemo[c]=nowRowMemo[c]=0;
  					continue;
 				}
				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;
 				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);//改行読み込み
 		}
  		printf("%d\n",spentsNo.size()-1);
 		if(scanf("%c",&nowP)==EOF)break;
 	}
 }