Marathon Match 64 初参加

夏休みで暇だったので、マラソンマッチに参加してみました。

【一言で分かる概要】コミケ
【ちゃんとした概要】こんな感じのマップがあって、セールスマンを歩かせる。なるべくたくさん売りつける。値段と仕入れる個数も決められる。利益を多くしたら勝ち。
f:id:tozangezan:20100902212123p:image

【最初の方針】
まず0.01点まで行くまでにそれなりにちゃんとしたことをしなければならない。

やること

  1. initの実装(代入だけでおk)
  2. セールスマンを動かす これが結構大変。家があるところをしっかり考えて、本来ありえない動きをしないようにしなければならない。
  3. 商品の仕入れ、利益を付けて販売。「買ってくれる最高金額」は少なくとも仕入れ値+10なのでそれに設定すればよい。仕入れる個数は適当に。
  4. これでプラス点取れるテストケースが出来るはず。

改良1

  1. 仕入れる個数の調整。前回に全部売れたら増やす、売れ残ったら減らす。
  2. 最初は各種類ではランダム個数に買っていたけどどうやら同じ個数ずつ買ったほうがよいらしい。
  3. なかなかバグは消えないので定期的にとってみる。この作業、つらい。
  4. 下の段についてしまったときの修正。(上から下に歩くプログラムを書いていたので、下の段についてから上に戻ることをやってみる。もちろんずらすのがベストだけど、そんなやり方とか思いつかない)

改良2 (id:kita_yutaに抜かれたので)

  1. 固まって家が存在している場所がある。そこを練り歩くと大幅に点が伸びる。
  2. またバグが出来る。それを直す。
  3. 以前から相当困っていたバグを直す。配列のx座標とy座標を間違えていただけだった
  4. 買う個数調整

これで何とかid:kita_yutaを抜かす。

改良3 (またid:kita_yutaに抜かれたので)

  1. 値段の調整
  2. 売れ残りやすい商品を仕分け。
  3. 正直言って無駄な改良ばっかりやっている。数値調整くらいしか点数上げる要因になっていない。
  4. 集合住宅練り歩きパターンより普通に歩くパターンのほうがたくさんの家を回れるとき、そっちを選ぶようにした。

何とかid:kita_yutaを抜かす。

改良4 (またid:kitayutaに抜かれたので)

  1. 値段の調整。これはかなり効いた。ここら辺からソースコードが荒れ始める。
  2. ↑によって絶対に買ってくれなくなった家に売り込むのをやめた。そして先に進むようにした。
  3. seedを1〜100まで試すことによるデバッグ

気がついたらid:kita_yutaより上に居る。

Javaじゃなかったら変数のネタが死んでたかも。Javaすご〜い。

これでSystem Test前スコアを86.02まで引き上げました。
現時点13位。たぶん下がります。
もしバグあったら散々言ってたid:kita_yutaにも負けるかも。バグあるなよ!!!

〜追記〜
結果が出た 16thくらい? なぜか黄色に。
No rated -> 1532
ほーらやっぱりid:kita_yutaに負けた。しかもバグだし。まあ実装は勝てないんだけど。

ソースコード (驚かないでね!!)

import java.util.*;
import java.io.*;

public class StreetSales{
	static String[] map;
	static int[] price;
	static int c;
	static int s;
	static int g;
	static int h;
	static int w;
	static int vk=-1;
	static int stt=-1;
	static int buys=0;
	static int before=0;
	static int[] humou;
	static int bx;
	static int by;
	static int lx;
	static int ly;
	static int day1col=0;
	static int day1row=2;
	static int cnTYPE;
	static int D;
	static int maxcol=0;
	static int maxrow=0;
	static int kensamax=0;
	static boolean debug=false;
	static int fiday=3;
	static int day=0;
	static int[] uke;
	static int[] newuke;
	static int[] buysec;
	static int[] urenokori;
	static int total=0;
	static int yos=0;
	static int rieki=10;
	static int ureni=200;
	static int nice=10;
	static double henka=0.02;
	static int nicesells;
	static double urenokorimax=999999999;
	static int urenokoritotal=999999999;
	static int shiwake[];
	static int ureindex=0;
	static boolean Day1Type=false;
	static boolean FLAG=true;
	static int uriage[];
	static boolean[][] slam;
	static int [][] higai;
	public static int 害活(int y,int x){
		String[] today=map.clone();
		String[] ret=new String[g+s+1];
		int col=x,row=y;
		boolean TES=false;
		boolean LUCK=false;
		boolean HOS=false;
		boolean Migi=true;
		boolean Shita=true;
		boolean Yasumi=true;
		int 剛=0;
		for(int i=g;i<g+s+1;i++){
			ret[i]=row+" "+col;
			if(today[row].charAt(col)=='X'){
				剛++;
				today[row]=today[row].substring(0,col)+"@"+today[row].substring(col+1);
				row=Integer.parseInt(ret[i-1].split(" ")[0]);
				col=Integer.parseInt(ret[i-1].split(" ")[1]);
			}
			if(i<g+s&&row<h-1&&col<w)if(today[row+1].charAt(col)=='X'){
				剛++;
				ret[++i]=(row+1)+" "+col;
				today[row+1]=today[row+1].substring(0,col)+"@"+today[row+1].substring(col+1);
				TES=false;
				/*if(i<g+s&&row>0&&today[row-1].charAt(col)=='X'){
					bt++;
					ret[++i]=row+" "+col;
					ret[++i]=(row-1)+" "+col;
					today[row-1]=today[row-1].substring(0,col)+"@"+today[row-1].substring(col+1);
				}*/
			}
			if(i<g+s&&row>0&&today[row-1].charAt(col)=='X'){
				剛++;
				ret[++i]=(row-1)+" "+col;
				today[row-1]=today[row-1].substring(0,col)+"@"+today[row-1].substring(col+1);
				TES=false;
			}
			if(TES&&i<g+s&&col>0&&today[row].charAt(col-1)=='X'){
				剛++;
				ret[++i]=(row)+" "+(col-1);
				TES=false;
				today[row]=today[row].substring(0,col-1)+"@"+today[row].substring(col);
				//i--;
				//continue;
			}
			if(TES&&i<g+s&&col<w-1&&today[row].charAt(col+1)=='X'){
				剛++;
				ret[++i]=(row)+" "+(col+1);
				TES=false;
				today[row]=today[row].substring(0,col+1)+"@"+today[row].substring(col+2);
				//i--;
				//continue;
			}
			if(TES){
				row--;
				if(row<h*3/4)TES=false;
			}
			else if(row%2>0){
				if(LUCK||HOS){
					col++;
				}
				else{
					col--;
					if(col<=Math.max(humou[row]-2,-1)){
						row++;
						col++;
						}
				}
				if(col>=w){
					if(Math.random()<0.2||HOS)row++;
					else row--;
					col=w-1;
				}
				}else{
				if(LUCK||HOS)col--;
				else{
					col++;
					if(col>=Math.min(humou[row]+2,w)){
						row++;
						
						col--;
					}
				}
				if(col<=-1){
					if(Math.random()<0.2||HOS)row++;
					else row--;
					col=0;
				}
			}
			if(row==1){
				if(LUCK){
					HOS=true;
					//row++;
				}
				LUCK=false;
			}
			if(row==-1){
				row+=2;
			}
			if(row==h){
				TES=true;
				LUCK=true;
				row-=2;
			}
			/*if(LUCK&&today[row].charAt(col)=='@'){
				row=Integer.parseInt(ret[i].split(" ")[0]);
				col=Integer.parseInt(ret[i].split(" ")[1]);
			}*/
			if(today[row].charAt(col)=='@'){
				row=Integer.parseInt(ret[i].split(" ")[0]);
				col=Integer.parseInt(ret[i].split(" ")[1]);
				//if(row==72)System.err.println("Here. ->"+col);
				if(today[row].charAt(col)=='@'){
					row=Integer.parseInt(ret[i-1].split(" ")[0]);
					col=Integer.parseInt(ret[i-1].split(" ")[1]);
				}
				if(LUCK&&row>1&&today[row-1].charAt(col)=='.'){
					//if(Math.random()>0.4)row--;
					//else row++;
					row--;
				}else if(LUCK&&row<h-1&&today[row+1].charAt(col)=='.'){
					row++;
				}
				else if(TES&&row>1&&col<w-1&&today[row].charAt(col+1)=='.')col++;
				else if(row<h-1&&today[row+1].charAt(col)=='.')row++;
				else if(col<w-1&&today[row].charAt(col+1)=='.'){
					col++;
				}
				else if(row>1&&today[row-1].charAt(col)=='.')row--;
				else col--;
				//System.out.println(row+" "+col);
				/*
				if(row==Integer.parseInt(ret[i].split(" ")[0])&&row<h-1&&today[row+1].charAt(col)=='.'){
					row++;
				}
				else if(row==Integer.parseInt(ret[i].split(" ")[0])&&row>0&&today[row-1].charAt(col)=='.'){
					row--;
				}
				*/
			}
		}
		return 剛;
	}

	public static String[] dayTrade(int[] visitedHouses){
		fiday--;
		day++;
		for(int i=0;i<h*w&&day>50&&day<=150;i++)
		if(visitedHouses[i]>=0)uke[visitedHouses[i]]++;
		for(int i=0;i<h*w&&day>=100&&day<250;i++)
		if(visitedHouses[i]>=0)newuke[visitedHouses[i]]++;
		
		if(day==150){
			total=0;
			for(int i=0;i<g;i++)total+=uke[i];
		}
		if(day==3){
			for(int i=0;i<h;i++){
				Arrays.fill(slam[i],false);
			}
		}
		String[] today=map.clone();
		String[] ret=new String[g+s+1];
		int n=4;
		int TYPE=cnTYPE;
		int bt=0;
		if(h*w<1000)n=4;
		int able=before;
		int sell=0;
		for(int i=0;i<visitedHouses.length;i++){
			if(visitedHouses[i]>=0)sell++;
			if(day>=180&&visitedHouses[i]>=0){
				higai[i/w][i%w]++;
			}
		}
		if(fiday==2||fiday==1)able=c/n;
		else if(fiday==0){
			able=(int)((double)vk*0.8);
		}
		else if(sell+buys==0)able=s/5;
		else if(sell==buys)able+=Math.max(1,(int)((double)buys*henka*4));
		else {
			henka=0.001;
			//henka=0;
			able-=Math.max(3,(int)((double)buys*henka*5));
		}
		//if(vk>=0)able=(int)((double)vk*0.8);
		buys=0;
		before=able;
		if(able>c)able=c;
		int bound=able;
		if(day>=220&&day%100==20){
			for(int i=0;i<h;i++){
				for(int j=0;j<w;j++){
					if(higai[i][j]==0&&slam[i][j]){
						map[i]=map[i].substring(0,j)+"@"+map[i].substring(j+1);
						slam[i][j]=false;
					}
				}
			}
		}
		if(day==250){
			urenokoritotal=0;
			urenokorimax=0;
			for(int i=0;i<g;i++){
				urenokori[i]=buysec[i]-newuke[i];
				if(urenokori[i]*100>buysec[i]*3){
					shiwake[i]=Math.max(3,(int)(3*(double)urenokori[i]/(double)buysec[i]*10));
					bound+=Math.max(3,(int)(3*(double)urenokori[i]/(double)buysec[i]*10));
				}
				urenokoritotal+=urenokori[i];
				if(urenokorimax<(double)urenokori[i]/(double)buysec[i]){
					urenokorimax=(double)urenokori[i]/(double)buysec[i];
					ureindex=i;
				}
			}
			//for(int i=0;i<g;i++)bound+=urenokori[i]*Math.max(2,bound/ureni)/urenokorimax;
			//bound+=urenokoritotal/=150;
			shiwake[ureindex]=Math.max(shiwake[ureindex],1);
		}
		able=bound;
		int []panai=new int[g];
		for(int i=0;i<g;i++)panai[i]=0;
		for(int i=0;i<bound%g;i++)panai[i]++;
		rieki=10;
		if(FLAG&&day>=100)rieki=10+day-100;
		if(FLAG&&day>=101){
			if(sell*(rieki-1)>(nicesells)*nice){
			//if(sell>nicesells){
				nicesells=sell;
				nice=rieki-1;
			}else{
				FLAG=false;
				//System.err.println(nice);
			}
			//System.err.println(sell*(rieki-1));
		}
		rieki=nice+1;
		able=Math.min(able,c);
		for(int i=0;i<g;i++){
			int d=bound/g;
			if(day>=150){
				d=bound*uke[i]/total;
				//System.err.println(day+" "+i+" "+d);
			}
			//System.err.println(Arrays.toString(uke));
			if(able==0)d=0;
			if(d>able)d=able;
			if(able<0){
				able=0;
				d=0;
			}
			if(d<0)d=0;
			if(i==g-1){
				ret[i]=Integer.toString(Math.max(0,able-shiwake[i]))+" "+(price[i]+rieki);
				buys+=Math.max(0,able-shiwake[i]);
			}
			else {
				ret[i]=Integer.toString(Math.max(0,d+panai[i]-shiwake[i]))+" "+(price[i]+rieki);
				able-=Math.max(0,d+panai[i]-shiwake[i]);
				buys+=Math.max(0,d+panai[i]-shiwake[i]);
			}
			if(day>=100&&day<250)buysec[i]+=Integer.parseInt(ret[i].split(" ")[0]);
			if(day==250)System.err.println(i+" "+buysec[i]+" "+newuke[i]+" "+shiwake[i]);
		}
		/*int at=0;
		int mc=price[0];
		for(int i=0;i<g;i++){
			if(mc>price[i]){
				mc=price[i];
				at=i;
			}
		}
		for(int i=0;i<g;i++){
			if(at==i)ret[i]=able+" "+(price[i]+(int)(Math.random()*5)+8);
			else ret[i]="0 0";
		}*/
		int col=0,row=0;
		if(TYPE==1){
			if((ly-by+2)/(D+1)<7&&w>25)row=by-1;
			else if(D==1)row=by+1;
			else row=by+yos;
			col=bx;
		}else{
			if((lx-bx+2)/(D+1)<7&&w>25)col=bx-1;
			else if(D==1)col=bx+1;
			else col=bx+yos;
			row=by;
		}
		if(day==1||Day1Type){
			row=day1row;
			col=day1col;
		}
		//System.err.println((ly-by+2)/(D+1));
		if(debug)System.err.println(bx+" "+by+" "+lx+" "+ly);
		int x=1;
		int y=0;
		boolean TES=false;
		boolean LUCK=false;
		boolean HOS=false;
		boolean Migi=true;
		boolean Shita=true;
		boolean Yasumi=true;
		if(TYPE==1)Shita=false;
		if(TYPE==2)Migi=false;
		for(int i=g;i<g+s+1;i++){
			
			//pw.println(row+" "+col);
			if(day>1&&!Day1Type&&TYPE==1&&row<=ly+1&&row>=by-1&&col>=bx-1&&col<=lx+1){
				ret[i]=row+" "+col;
				if(i<g+s&&row<h-1&&col<w&&col>=0&&today[row+1].charAt(col)=='X'){
					bt++;
					ret[++i]=(row+1)+" "+col;
					slam[row+1][col]=true;
					today[row+1]=today[row+1].substring(0,col)+"@"+today[row+1].substring(col+1);
				}
				if(i<g+s&&row>0&&col<w&&col>=0&&today[row-1].charAt(col)=='X'){
					bt++;
					ret[++i]=(row-1)+" "+col;
					slam[row-1][col]=true;
					today[row-1]=today[row-1].substring(0,col)+"@"+today[row-1].substring(col+1);
				}
				if(i<g+s&&Shita&&col<w-1&&today[row].charAt(col+1)=='X'){
					bt++;
					ret[++i]=row+" "+(col+1);
					slam[row][col+1]=true;
					today[row]=today[row].substring(0,col+1)+"@"+today[row].substring(col+2);
				}
				if(i<g+s&&Shita&&col>0&&today[row].charAt(col-1)=='X'){
					bt++;
					ret[++i]=row+" "+(col-1);
					slam[row][col-1]=true;
					today[row]=today[row].substring(0,col-1)+"@"+today[row].substring(col);
				}
				if(Shita){
					row++;
					if(Migi){
						if(D==1&&Yasumi&&today[row].charAt(col+1)=='.'){
							Yasumi=false;
						}else if(today[row].charAt(col+1)=='.'){
							Shita=false;
							Yasumi=true;
						}
					}else{
						if(D==1&&Yasumi&&today[row].charAt(col-1)=='.'){
							Yasumi=false;
						}else if(today[row].charAt(col-1)=='.'){
							Shita=false;
							Yasumi=true;
						}
					}
				}else if(Migi){
					col++;
					if(col==lx+1&&row==ly+1)TYPE=0;
					else if(col>lx&&row<=ly+1){
						Migi=false;
						Shita=true;
					} 
				}else{
					col--;
					//System.err.println(col);
					if(col==bx-1&&row==ly+1)TYPE=0;
					else if(col<bx&&row<=ly+1){
						Migi=true;
						Shita=true;
					}
				}
			//}else if(type==1&&row<=y2+1&&row>=y1-1&&col>=x1-1&&col<=x2+1){
				//if(!(row<=ly+1&&row>=by-1&&col>=bx-1&&col<=lx+1))TYPE=0;
			}else if(day>1&&!Day1Type&&TYPE==2&&row<=ly+1&&row>=by-1&&col>=bx-1&&col<=lx+1){
				//System.err.println(" LY "+ly+" BY "+by+" BX "+bx+" LX "+lx+" W "+w+" H "+h);
				ret[i]=row+" "+col;
				if(i<g+s&&col<w-1&&today[row].charAt(col+1)=='X'){
					bt++;
					ret[++i]=(row)+" "+(col+1);
					slam[row][col+1]=true;
					today[row]=today[row].substring(0,col+1)+"@"+today[row].substring(col+2);
				}
				if(i<g+s&&col>0&&today[row].charAt(col-1)=='X'){
					bt++;
					ret[++i]=(row)+" "+(col-1);
					slam[row][col-1]=true;
					today[row]=today[row].substring(0,col-1)+"@"+today[row].substring(col);
				}
				if(i<g+s&&Migi&&row<h-1&&today[row+1].charAt(col)=='X'){
					bt++;
					ret[++i]=(row+1)+" "+col;
					slam[row+1][col]=true;
					today[row+1]=today[row+1].substring(0,col)+"@"+today[row+1].substring(col+1);
				}
				if(i<g+s&&Migi&&row>0&&today[row-1].charAt(col)=='X'){
					bt++;
					ret[++i]=(row-1)+" "+col;
					slam[row-1][col]=true;
					today[row-1]=today[row-1].substring(0,col)+"@"+today[row-1].substring(col+1);
				}
				if(Migi){
					col++;
					if(Shita){
						if(D==1&&Yasumi&&today[row+1].charAt(col)=='.'){
							Yasumi=false;
						}else if(today[row+1].charAt(col)=='.'){
							Migi=false;
							Yasumi=true;
						}
					}else{
						if(D==1&&Yasumi&&today[row-1].charAt(col)=='.'){
							Yasumi=false;
						}else if(today[row-1].charAt(col)=='.'){
							Migi=false;
							Yasumi=true;
						}
					}
				}else if(Shita){
					row++;
					if(row>ly&&col<lx+1){
						Shita=false;
						Migi=true;
					} 
				}else{
					row--;
					if(row<by&&col<lx+1){
						Migi=true;
						Shita=true;
					}
				}
			//}else if(type==1&&row<=y2+1&&row>=y1-1&&col>=x1-1&&col<=x2+1){
				//if(!(row<=ly+1&&row>=by-1&&col>=bx-1&&col<=lx+1))TYPE=0;
			}

			else{
				if(!Day1Type&&day>1);TYPE=0;
				ret[i]=row+" "+col;
				//if(TES)System.err.println("TES");
				if(today[row].charAt(col)=='X'){
					bt++;
					today[row]=today[row].substring(0,col)+"@"+today[row].substring(col+1);
					slam[row][col]=true;
					row=Integer.parseInt(ret[i-1].split(" ")[0]);
					col=Integer.parseInt(ret[i-1].split(" ")[1]);
					
				}
				if(i<g+s&&row<h-1&&col<w)if(today[row+1].charAt(col)=='X'){
					bt++;
					ret[++i]=(row+1)+" "+col;
					slam[row+1][col]=true;
					today[row+1]=today[row+1].substring(0,col)+"@"+today[row+1].substring(col+1);
					TES=false;
				}
				if(i<g+s&&row>0&&today[row-1].charAt(col)=='X'){
					bt++;
					ret[++i]=(row-1)+" "+col;
					slam[row-1][col]=true;
					today[row-1]=today[row-1].substring(0,col)+"@"+today[row-1].substring(col+1);
					TES=false;
				}
				if(TES&&i<g+s&&col>0&&today[row].charAt(col-1)=='X'){
					bt++;
					ret[++i]=(row)+" "+(col-1);
					slam[row][col-1]=true;
					//TES=false;
					today[row]=today[row].substring(0,col-1)+"@"+today[row].substring(col);
					//i--;
					//continue;
				}
				if(TES&&i<g+s&&col<w-1&&today[row].charAt(col+1)=='X'){
					bt++;
					ret[++i]=(row)+" "+(col+1);
					slam[row][col+1]=true;
					//TES=false;
					today[row]=today[row].substring(0,col+1)+"@"+today[row].substring(col+2);
					//i--;
					//continue;
				}
				if(TES){
					row--;
					if(row<h*3/4)TES=false;
				}
				else if(row%2>0){
					if(LUCK||HOS){
						col++;
					}
					else{
						col--;
						if(col<=Math.max(humou[row]-2,-1)){
							row++;
							col++;

						}
					}
					if(col>=w){
						if(Math.random()<0.2||HOS)row++;
						else row--;
						col=w-1;
					}

				}else{
					if(LUCK||HOS)col--;
					else{
						col++;
						if(col>=Math.min(humou[row]+2,w)){
							row++;
							
							col--;
						}
					}
					if(col<=-1){
						if(Math.random()<0.2||HOS)row++;
						else row--;
						col=0;
					}
				}
				if(row==1){
					if(LUCK){
						HOS=true;
						//row++;
					}
					LUCK=false;
				}
				if(row==-1){
					row+=2;
				}
				if(row==h){
					if(HOS)HOS=false;
					TES=true;
					LUCK=true;
					row-=2;
				}
				//System.err.println(row+" "+col);
				/*if(LUCK&&today[row].charAt(col)=='@'){
					row=Integer.parseInt(ret[i].split(" ")[0]);
					col=Integer.parseInt(ret[i].split(" ")[1]);
				}*/
				if(today[row].charAt(col)=='@'){
					//System.err.println("CALL");
					row=Integer.parseInt(ret[i].split(" ")[0]);
					col=Integer.parseInt(ret[i].split(" ")[1]);
					
					//if(row==72)System.err.println("Here. ->"+col);
					if(today[row].charAt(col)=='@'){
						row=Integer.parseInt(ret[i-1].split(" ")[0]);
						col=Integer.parseInt(ret[i-1].split(" ")[1]);
					}
					/*if(today[row].charAt(col)=='@'){
						row=Integer.parseInt(ret[i-2].split(" ")[0]);
						col=Integer.parseInt(ret[i-2].split(" ")[1]);
					}*/
					if(LUCK&&row>1&&today[row-1].charAt(col)=='.'){
						//if(Math.random()>0.4)row--;
						//else row++;
						row--;
					}else if(LUCK&&col>0&&today[row].charAt(col-1)=='.'){
						col--;
					}else if(LUCK&&col<w-1&&today[row].charAt(col+1)=='.'){
						col++;
					}
					else if(TES&&row>1&&col<w-1&&today[row].charAt(col+1)=='.')col++;
					else if(row<h-1&&today[row+1].charAt(col)=='.')row++;
					else if(col<w-1&&today[row].charAt(col+1)=='.'){
						col++;
					}
					else if(row>1&&today[row-1].charAt(col)=='.')row--;
					else col--;
					//System.out.println(row+" "+col);
					/*
					if(row==Integer.parseInt(ret[i].split(" ")[0])&&row<h-1&&today[row+1].charAt(col)=='.'){
						row++;
					}
					else if(row==Integer.parseInt(ret[i].split(" ")[0])&&row>0&&today[row-1].charAt(col)=='.'){
						row--;
					}
					*/
				}
			}
		if(debug){
			System.err.println(ret[i]);
			for(int j=0;j<h;j++)System.err.println(today[j]);
			System.err.println();
		}
		}
		if(day==2){
			if(vk>=bt)Day1Type=true;
			else vk=bt;
		}
		if(vk==-1)vk=bt;
		return ret;
	}
	
	
	public static int init(String[] districtMap,int[] warehousePrices,int C,int S){
		map=districtMap;
		price=warehousePrices;
		c=C;
		s=S;
		g=price.length;
		uke=new int[g];
		newuke=new int[g];
		h=districtMap.length;
		w=districtMap[0].length();
		buysec=new int[g];
		urenokori=new int[g];
		shiwake=new int[g];
		humou=new int[h];
		uriage=new int[100];
		slam=new boolean[h][w];
		higai=new int[h][w];
		for(int i=0;i<h;i++){
			if(i%2==0){
				humou[i]=0;
				for(int j=0;j<w;j++){
					if(i>0&&map[i-1].charAt(j)=='X'){
						humou[i]=j;
						//break;
					}else if(i<h-1&&map[i+1].charAt(j)=='X'){
						humou[i]=j;
						//break;
					}
				}
			}else {
				humou[i]=w-1;
				for(int j=w-1;j>=0;j--){
					if(i>0&&map[i-1].charAt(j)=='X'){
						humou[i]=j;
						//break;
					}else if(i<h-1&&map[i+1].charAt(j)=='X'){
						humou[i]=j;
						//break;
					}
				}
			}
		}
		int x1=w,x2=0,y1=h,y2=0;
		int x3=w,y3=h,x4=0,y4=0;
		int type;
		int dx=0;
		int dy=0;
		int dist=0;
		for(int i=0;i<g;i++)uke[i]=0;
		for(int i=0;i<h;i++){
			for(int j=1;j<w;j++){
				if(map[i].charAt(j)=='X'&&map[i].charAt(j-1)=='X'){
					x1=Math.min(x1,j-1);
					y1=Math.min(y1,i);
					y2=Math.max(y2,i);
					x2=Math.max(x2,j);
				}
			}
		}
		for(int j=0;j<w;j++){
			for(int i=1;i<h;i++){
				if(map[i].charAt(j)=='X'&&map[i-1].charAt(j)=='X'){
					x3=Math.min(x3,j);
					y3=Math.min(y3,i-1);
					x4=Math.max(x4,j);
					y4=Math.max(y4,i);
				}
			}
		}
		if(x1<w&&x3==w&&x4==0){
			type=1;
			dist=1;
		}
		else if(x3<w&&x1==w&&x2==0){
			type=2;
			x1=x3;
			x2=x4;
			y1=y3;
			y2=y4;
			dist=1;
		}
		else{
			int dis1=0;
			int dis2=0;
			for(int i=y3;i<=y4;i++){
				if(i<h&&x1<w&&map[i].charAt(x1)=='.'){
					dis1=i-y1;
					break;
				}
			}
			for(int i=x1;i<=x2;i++){
				if(y1<h&&i<w&&map[y1].charAt(i)=='.'){
					dis2=i-x1;
					break;
				}
			}
			if(dis1<dis2||(dis1==dis2&&x2-x1>y4-y3)){
				type=1;
				dist=dis2;
				yos=dis1;
				x1=x3;
				x2=x4;
				y1=y3;
				y2=y4;
			}else{
				type=2;
				dist=dis1;
				yos=dis2;
			}
		}
		cnTYPE=type;
		D=dist;
		bx=x1;
		by=y1;
		lx=x2;
		ly=y2;
		/*
		int 今の剛=0;
		int 生卵=0;
		for(int i=0;i<w;i++){
			if(今の剛<(生卵=害活(0,i))){
				今の剛=生卵;
				day1row=0;
				day1col=i;
			}
		}
		for(int i=0;i<h;i++){
			if(今の剛<(生卵=害活(i,0))){
				今の剛=生卵;
				day1col=0;
				day1row=i;
			}
		}
		System.err.println(day1row+" "+day1col);
		*/
		return 0;
	}
	
	public static void main(String args[]) throws Exception{
		Scanner q=new Scanner(System.in);
		int H=q.nextInt();
		String [] m=new String[H];
		for(int i=0;i<H;i++)m[i]=q.next();
		int W=m[0].length();
		int G=q.nextInt();
		int[] ware=new int[G];
		for(int i=0;i<G;i++)ware[i]=q.nextInt();
		int C=q.nextInt(),S=q.nextInt();
		init(m,ware,C,S);
		for(int day=0;day<3000;day++){
			int takeshi[]=new int[H*W];
			for(int i=0;i<H*W;i++)takeshi[i]=q.nextInt();
			String[] route=dayTrade(takeshi);
			int r=route.length;
			System.out.println(r);
			for(int i=0;i<r;i++)
				System.out.println(route[i]);
		}
	}
}