「AOJ再挑戦66~70」の編集履歴(バックアップ)一覧に戻る

AOJ再挑戦66~70 - (2014/01/31 (金) 07:40:48) の編集履歴(バックアップ)


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

問66 Tic Tac Toe

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

自分で考えられる限りの短縮を図ったものの平凡なショートコーディングになった。
この問題昔掲示板でヒントはもらって書いたのだけど、今回はその時より短くなっている。
短さ1位の人のコードは想像もつかないがAOJの外には1位の人より上がいるのがネットの世界。
すごいと思う。
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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0067
格子上のデータで海と陸があらわされている島の数を数えよという問題。
解法
この問題12*12で標準出力から読み込む問題ですが。
島と海のデータがテキストファイルで与えられデータが大きくなった場合。
たとえば数十万行*数十万列のデータでも計算できるようなアルゴリズムを構築しました。
計算量は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;
	}
}