Pages

Saturday 15 December 2012

UVA - 10855 - Rotated square

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        while(true){
            String[]str=br.readLine().split(" ");
            int n=Integer.parseInt(str[0]);
            int m=Integer.parseInt(str[1]);
            if(n==0 && m==0){
                break;
            }
            char [][]arr=new char[n][n];
            for(int i=0;i<n;i++){
                String temp=br.readLine();
              for(int j=0;j<n;j++){
                 arr[i][j]=temp.charAt(j);
              } 
            }
            char [][]arr2=new char[m][m];
            for(int i=0;i<m;i++){
                String temp=br.readLine();
              for(int j=0;j<m;j++){
                 arr2[i][j]=temp.charAt(j);
              } 
            }
            int[]ans=new int[4];
            ans[0]=search(arr, arr2);
            ans[1]=search(arr, rotate90(arr2));
            ans[2]=search(arr, rotate180(arr2));
            ans[3]=search(arr, rotate270(arr2));
            sb.append(ans[0]).append(" ").append(ans[1]).append(" ").append(ans[2]).append(" ").append(ans[3]).append("\n");
        }
        System.out.print(sb);
    }
   
    static public char[][] rotate90(char[][] arr){
        int x=arr.length,y=arr[0].length;
        char[][]temp=new char[x][y];
        for(int i=0;i<x;i++){
          for(int j=0;j<y;j++){
              temp[i][j]=arr[y-j-1][i];
            } 
        }
        return temp;
    }
   
   static public char[][] rotate180(char[][] arr){
        int x=arr.length,y=arr[0].length;
        char[][]temp=new char[x][y];
        for(int i=0;i<x;i++){
          for(int j=0;j<y;j++){
              temp[i][j]=arr[x-i-1][y-j-1];
            } 
        }
        return temp;
    }
  
    static public char[][] rotate270(char[][] arr){
        int x=arr.length,y=arr[0].length;
        char[][]temp=new char[x][y];
        for(int i=0;i<x;i++){
          for(int j=0;j<y;j++){
              temp[i][j]=arr[j][x-i-1];
            } 
        }
        return temp;
    }
   
    static int search(char[][]big,char[][]small){
        int counter=0;
        for(int l=0;l<big.length-small.length+1;l++){
            for(int z=0;z<big[0].length-small[0].length+1;z++){
                boolean flag=true;
                for(int i=z, x=0;x<small.length;i++,x++){
                   for(int j=l,y=0;y<small[0].length;j++,y++){
                       if(big[i][j]!=small[x][y]){
                           flag=false;
                           break;
                       }
                    }
                   if(!flag){
                       break;
                   }
                }
                if(flag){
                    counter++;
                }
            }
        }
        return counter;
    }
}

No comments:

Post a Comment