Submission #2083829

---

Source Code Expand

import java.util.*;
//import java.io.BufferedWriter;
//import java.io.File;
//import java.io.FileWriter;

class Main{

	public static void main(String args[]) throws Exception{


		long start = System.currentTimeMillis();
		Random rnd = new Random();

		Scanner sc = new Scanner(System.in);

		int H = sc.nextInt();
		int W = sc.nextInt();
		int K = sc.nextInt();

		int map[][] = new int[H][W];
		boolean flag[][] = new boolean[H][W];

		for(int h=0;h<H;h++){
			String st = sc.next();
			for(int w=0;w<W;w++){
				char ch = st.charAt(w);
				map[h][w] = Character.getNumericValue(ch);
				if(map[h][w] == 0) flag[h][w] = true;
				else flag[h][w] = false;
			}
		}

		int count = 0;
		ArrayList<Integer> ansx = new ArrayList<>();
		ArrayList<Integer> ansy = new ArrayList<>();

		int x=0;
		int y=0;

		out:while((System.currentTimeMillis()-start)<9000){
			
			ArrayList<Integer> neigx = new ArrayList<>();
			ArrayList<Integer> neigy = new ArrayList<>();

			int ax[] = new int[8];
			int ay[] = new int[8];

			while(flag[y][x]){
				x++;
				if((x+1)/W == 1){ y++; x = 0;} 
				if((y+1)/H == 1) break out;
			}

			ax[0] = x;
			ay[0] = y;	
			flag[y][x] = true;

			if(y>0 && !flag[y-1][x])  { neigx.add(x);   neigy.add(y-1); }
			if(y<H-1 && !flag[y+1][x]){ neigx.add(x);   neigy.add(y+1); }
			if(x>0 && !flag[y][x-1])  { neigx.add(x-1); neigy.add(y);   }
			if(x>W-1 && !flag[y][x+1]){ neigx.add(x+1); neigy.add(y);   }

			if(neigx.size()==0){
				continue;	
			} 

			for(int k=1;k<K;k++){
				int max = getMax(map,neigx,neigy);
				ax[k] = neigx.get(max);
				ay[k] = neigy.get(max);

				flag[ay[k]][ax[k]] = true;

				neigx.remove(max);
				neigy.remove(max);

				if(ay[k]>0 && !flag[ay[k]-1][ax[k]])  { neigx.add(ax[k]);   neigy.add(ay[k]-1); flag[ay[k]-1][ax[k]] = true;}
				if(ay[k]<H-1 && !flag[ay[k]+1][ax[k]]){ neigx.add(ax[k]);   neigy.add(ay[k]+1); flag[ay[k]+1][ax[k]] = true;}
				if(ax[k]>0 && !flag[ay[k]][ax[k]-1])  { neigx.add(ax[k]-1); neigy.add(ay[k]); flag[ay[k]][ax[k]-1] = true;   }
				if(ax[k]>W-1 && !flag[ay[k]][ax[k]+1]){ neigx.add(ax[k]+1); neigy.add(ay[k]); flag[ay[k]][ax[k]+1] = true; }

				if(neigx.size()==0){
					continue out;	
				}	 

			}

			for(int n=0;n<K;n++){
				ansx.add(ax[n]+1);
				ansy.add(ay[n]+1);
			}
			count++;
		}

		//File file = new File("output.txt");
		//BufferedWriter bw = new BufferedWriter(new FileWriter(file));

		//bw.write(count);
		//bw.newLine();
		System.out.println(count);

		for(int n=0;n<count;n++){
			for(int k=0;k<K;k++){
				System.out.println(ansy.get(n*K+k)+" "+ansx.get(n*K+k));
		//		bw.write(ansy.get(n*K+k)+" "+ansx.get(n*K+k));
		//		bw.newLine();
			}
		}
		//bw.flush();
	}

	private static int getMax(int m[][],ArrayList<Integer> x,ArrayList<Integer> y){
		int val = m[x.get(0)][y.get(0)];
		int tmp = 0;
		int k = 1;
		while(val!=9 && k<x.size()){
			if(val<m[x.get(k)][y.get(k)]){
				tmp = k;
				val = m[x.get(k)][y.get(k)];
			}
			k++;
		}

		return tmp;
	}
}

Submission Info

Judge Result