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

---

「AOJ再挑戦91～95」を以下のとおり復元します。

---

*問91　Blur
布の色の濃さのデータからどのように染料がたらされたのか逆算する問題。

解法
地道に一マスずつ動的計画法を適用しました。
コードはマトリックス化して配列にしておくべきだったかも。
めんどくさいので解説とか書かない。


 #include<stdio.h>
 #include<vector>
 #include<set>
 
 struct S{
 	int n,x,y;
 	int map[10][10];
 	std::vector<int> ansXs,ansYs,ansSize;
 	bool operator<(const S& s)const{
 		if(n!=s.n)return n<s.n;
		if(y!=s.y)return y<s.y;
 		if(x!=s.x)return x<s.x;
 		for(int i=-2;i<=2;i++){
 			int dy=y+i;
 			if(0<=dy&&dy<=9){
 				for(int x=0;x<=9;x++){
 					if(map[dy][x]!=s.map[dy][x])return map[dy][x]<s.map[dy][x];
 				}
 			}
 		}
 		return false;
 	}
 	void commit(int size){
 		ansXs.push_back(x);
		ansYs.push_back(y);
 		ansSize.push_back(size);
 	}
 	void commitPop(){
 		ansXs.pop_back();
 		ansYs.pop_back();
 		ansSize.pop_back();
 	}
 
 	bool isNextOK(){
 		if(y<2)return true;
 		if(2<=y&&y<=7){
 			return map[y-2][x]==0;
 		}
		if(y==8){
 			if(map[y-2][x]>0)return false;
 			if(x==9){
 				return n==0&&(map[y-1][x] | map[y][x] | map[y+1][x] | map[y-1][x-1] | map[y][x-1] | map[y+1][x-1])==0;
 			}else if(x>0){
 				return (map[y-1][x-1] | map[y][x-1] | map[y+1][x-1])==0;
 			}else{
 				return true;
 			}
 		}
 		return false;
	}
  	
 	bool isS_OK(){
 		if(n<=0)return false;
 		if(0<x&&x<9&&0<y&&y<9){
 			return map[y-1][x]>0 && map[y+1][x]>0 && map[y][x+1]>0 && map[y][x-1]>0 && map[y][x]>0;
 		}else{
			return false;
 		}
 	}
 	bool isM_OK(){
 		if(0<x&&x<9&&0<y&&y<9){
  			bool t =map[y-1][x-1]>0 && map[y-1][x+1]>0 && map[y+1][x+1]>0 && map[y+1][x-1]>0;
			return t&&isS_OK();
  		}else{
 			return false;
		}
 	}
 	bool isL_OK(){
 		if(1<x&&x<8&&1<y&&y<8){
  			bool t =map[y-2][x]>0&&map[y+2][x]>0&&map[y][x+2]>0&&map[y][x-2]>0;
			return t&&isM_OK();
 		}else{
  			return false;
		}
 	}
 	void changeS(int add){
 		map[y-1][x]+=add;
 		map[y+1][x]+=add;
 		map[y][x-1]+=add;
 		map[y][x+1]+=add;
 		map[y][x]+=  add;
 		n+=add;
 	}
 	
 	void changeM(int add){
 		map[y-1][x-1]+=add;
  		map[y-1][x+1]+=add;
 		map[y+1][x-1]+=add;
 		map[y+1][x+1]+=add;
 		changeS(add);
 	}
 	
 	void changeL(int add){
 		map[y+2][x]+=add;
 		map[y-2][x]+=add;
  		map[y][x+2]+=add;
		map[y][x-2]+=add;
  		changeM(add);
 	}
 
 };
 
 void searchS(std::set<S>& next,S& s1){
 	if(s1.isS_OK()){
 		s1.changeS(-1);
 		s1.commit(1);
 		searchS(next,s1);
  		if(s1.isNextOK()==true){
 			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeS(1);
 	}
 }
 void searchM(std::set<S>& next,S& s1){
 	searchS(next,s1);
 	if(s1.isM_OK()){
 		s1.changeM(-1);
 		s1.commit(2);
  		searchM(next,s1);
 		if(s1.isNextOK()==true){
  			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeM(1);
	}
 }
 	
 	
 void searchL(std::set<S>& next,S &s1){
 	searchM(next,s1);
 	if(s1.isL_OK()){
 		s1.changeL(-1);
 		s1.commit(3);
 		searchL(next,s1);
 		if(s1.isNextOK()==true){
 			next.insert(s1);
 		}
 		s1.commitPop();
 		s1.changeL(1);
 	}
 }
 
 void calc(S seed){
 	std::set<S>::iterator it;
 	S s1;
 	std::set<S> memo,next;
 	memo.insert(seed);
 	for(int y=1;y<=8;y++){
 		for(int x=1;x<=9;x++){
  			for(it=memo.begin();it!=memo.end();it++){
 				s1=(*it);
 				s1.x=x;
 				s1.y=y;
 				searchL(next,s1);
 				if(s1.isNextOK())next.insert(s1);
 			}
 			memo.clear();
 			memo.insert(next.begin(),next.end());
 			next.clear();
 		}
 	}
  	it=memo.begin();
 	s1=(*it);
 	for(int i=0;i<s1.ansXs.size();i++){
 		printf("%d %d %d\n",s1.ansXs[i],s1.ansYs[i],s1.ansSize[i]);
 	}
 }
 
  
 
 
 int main(){
  	S seed;
 	scanf("%d",&seed.n);
 	for(int i=0;i<10;i++){
 		for(int j=0;j<10;j++){
 			scanf("%d",&seed.map[i][j]);
  		}
 	}
 	calc(seed);
 }

---

復元してよろしいですか？