UVA - 232 - Crossword Answers

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        int cases=1;
        while(true){
           StringTokenizer st=new StringTokenizer(br.readLine());
           int n=Integer.parseInt(st.nextToken());
           if(n==0)
               break;
           if(cases>1){
               sb.append("\n");
           }
           sb.append(String.format("puzzle #%d:\n", cases));
           int m=Integer.parseInt(st.nextToken());
           char[][]arr=new char[n][m];
           char[][]pos=new char[n][m];
           for(int i=0;i<n;i++){
               arr[i]=br.readLine().toCharArray();
           }
           for(int i=0;i<n;i++){
               boolean flag=true;
              for(int j=0;j<m;j++){
                  if(arr[i][j]=='*'){
                      flag=true;
                  }else{
                      if(flag){
                         flag=false;
                         pos[i][j]='n';
                      }
                  }
              }
           }
           for(int i=0;i<m;i++){
               boolean flag=true;
              for(int j=0;j<n;j++){
                  if(arr[j][i]=='*'){
                      flag=true;
                  }else{
                      if(flag){
                         flag=false;
                         pos[j][i]='n';
                      }
                  }
              }
           }
           int[][]posX=new int[n][m];
           for(int i=0,p=1;i<n;i++){
              for(int j=0;j<m;j++){
                  if(pos[i][j]=='n'){
                      posX[i][j]=p++;
                  }
              }
           }
           LinkedList<String> list=new LinkedList<String>();
           sb.append("Across\n");
           for(int i=0;i<n;i++){
               boolean flag=true;
               StringBuilder temp=new StringBuilder();
              for(int j=0;j<m;j++){
                  if(arr[i][j]=='*'){
                      if(!flag){
                          list.add(temp.toString());
                          temp=new StringBuilder();
                      }
                      flag=true;
                  }else{
                      if(flag){
                         String str=String.format("%3d.", posX[i][j]) ; 
                         temp.append(str);
                         flag=false;
                      }
                      temp.append(arr[i][j]);
                  }
              }
              if(!flag){
                list.add(temp.toString());
                temp=new StringBuilder();
              }
           }
           Collections.sort(list);
           while(!list.isEmpty()){
               sb.append(list.remove()).append("\n");
           }
           sb.append("Down\n");
           LinkedList<String> list2=new  LinkedList<String>();
           for(int i=0;i<m;i++){
               boolean flag=true;
               StringBuilder temp=new StringBuilder();
              for(int j=0;j<n;j++){
                  if(arr[j][i]=='*'){
                      if(!flag){
                          list2.add(temp.toString());
                          temp=new StringBuilder();
                      }
                      flag=true;
                  }else{
                      if(flag){
                         String str=String.format("%3d.", posX[j][i]) ; 
                         temp.append(str);
                         flag=false;
                      }
                      temp.append(arr[j][i]);
                  }
              }
              if(!flag){
                list2.add(temp.toString());
                temp=new StringBuilder();
              }
           }
           Collections.sort(list2);
           while(!list2.isEmpty()){
               sb.append(list2.remove()).append("\n");
           }
           cases++;
        }
        System.out.print(sb);
    }
}