Tag Archives: uva

UVA 10855 – Rotated square

This problem has an interesting algorithm used it in. How to rotate a square matrix. Basically if you want to rotate a square matrix by 90 degress you can notice that 4 elements in the 2D array get changed in a cyclical manner. You can just repeat this for (almost) one quarter of the square that you are rotating.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P10855 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    StringTokenizer st = null;

    while (true) {

      st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());
      int n = Integer.parseInt(st.nextToken());
      if (N + n == 0)
        break;

      char[][] big = new char[N][N];
      for (int i = 0; i < N; i++) {
        char[] line = br.readLine().toCharArray();
        for (int j = 0; j < N; j++) {
          big[i][j] = line[j];
        }
      }

      char[][] small = new char[n][n];
      for (int i = 0; i < n; i++) {
        char[] line = br.readLine().toCharArray();
        for (int j = 0; j < n; j++) {
          small[i][j] = line[j];
        }
      }

      out.print(check(big, small) + " ");
      rotate(small);
      out.print(check(big, small) + " ");
      rotate(small);
      out.print(check(big, small) + " ");
      rotate(small);
      out.println(check(big, small));
    }
    
    out.close();
    br.close();
  }

  private static int check(char[][] big, char[][] small) {
    int ans = 0;
    for (int i = 0; i <= big.length - small.length; i++) {
      for (int j = 0; j <= big.length - small.length; j++) {
        if (big[i][j] == small[0][0]) {
          boolean found = true;
          for (int k = 0; k < small.length; k++) {
            for (int l = 0; l < small.length; l++) {
              if (big[i + k][j + l] != small[k][l]) {
                found = false;
                break;
              }
            }
          }
          if (found)
            ans++;
        }
      }
    }
    return ans;
  }

  private static void rotate(char[][] m) {
    int n = m.length;
    for (int i = 0; i < n / 2; i++)
      for (int j = 0; j < (n + 1) / 2; j++) {
        char temp = m[i][j];
        m[i][j] = m[n - 1 - j][i];
        m[n - 1 - j][i] = m[n - 1 - i][n - 1 - j];
        m[n - 1 - i][n - 1 - j] = m[j][n - 1 - i];
        m[j][n - 1 - i] = temp;
      }
  }
}