Lát gạch 2

latgach2.cpp

package com.vtcc.antispam.hieunv.latgach;

import java.util.Scanner;

/**
 * Created by HieuNguyen on 02/26/2017.
 */
public class Runner {
    static int s, x, y, a[][], val = 0;

    static void init() {
        Scanner sc = new Scanner(System.in);
        s = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        a = new int[s + 1][s + 1];
        a[x][y] = -1;
    }

    static void solve(int s, int x, int y, int c, int h) {
        val++;
        if (s == 2) {
            if (a[c][h] == 0) a[c][h] = val;
            if (a[c + 1][h] == 0) a[c + 1][h] = val;
            if (a[c][h + 1] == 0) a[c][h + 1] = val;
            if (a[c + 1][h + 1] == 0) a[c + 1][h + 1] = val;
        } else {
            if (x < c + s / 2) {
                if (y < h + s / 2) {
                    a[c + s / 2][h + s / 2] = val;
                    a[c + s / 2 - 1][h + s / 2] = val;
                    a[c + s / 2][h + s / 2 - 1] = val;

                    solve(s/2,x,y,c,h);
                    solve(s/2,c+s/2,h+s/2-1,c+s/2,h);
                    solve(s/2,c+s/2-1,h+s/2,c,h+s/2);
                    solve(s/2,c+s/2,h+s/2,c+s/2,h+s/2);
                } else {
                    a[c + s / 2][h + s / 2] = val;
                    a[c + s / 2][h + s / 2 - 1] = val;
                    a[c + s / 2 - 1][h + s / 2 - 1] = val;

                    solve(s/2,c + s / 2 -1,h + s / 2-1,c,h);
                    solve(s/2,c+s/2,h+s/2-1,c+s/2,h);
                    solve(s/2,x,y,c,h+s/2);
                    solve(s/2,c+s/2,h+s/2,c+s/2,h+s/2);
                }
            } else {
                if (y < h + s / 2) {
                    a[c + s / 2][h + s / 2] = val;
                    a[c + s / 2 - 1][h + s / 2] = val;
                    a[c + s / 2 - 1][h + s / 2 - 1] = val;

                    solve(s/2,c+s/2-1,c+s/2-1,c,h);
                    solve(s/2,x,y,c+s/2,h);
                    solve(s/2,c+s/2-1,h+s/2,c,h+s/2);
                    solve(s/2,x,y,c+s/2,h+s/2);

                } else {
                    a[c + s / 2 - 1][h + s / 2] = val;
                    a[c + s / 2 - 1][h + s / 2 - 1] = val;
                    a[c + s / 2][h + s / 2 - 1] = val;

                    solve(s/2,c+s/2-1,h+s/2-1,c,h);
                    solve(s/2,c+s/2,h+s/2-1,c+s/2,h);
                    solve(s/2,c+s/2-1,h+s/2,c,h+s/2);
                    solve(s/2,c+s/2-1,h+s/2,c,h+s/2);
                    solve(s/2,x,y,c+s/2,h+s/2);
                }
            }
        }
    }

    static void print() {
        for (int i = 1; i <= s; i++) {
            for (int j = 1; j <= s; j++) {
                System.out.print(a[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        init();
        solve(s, x, y, 1, 1);
        a[x][y] = 0;
        print();
    }
}

Đề bài.txt

Có một khoảng sân hình vuông kích thước n x n ô vuông, gồm n hàng và n cột, trong đó n là số nguyên có dạng lũy thừa của 2 (n = 2k). Đánh số hàng từ 1 đến n theo thứ tự từ trên xuống dưới, đánh số cột từ 1 đến n theo thứ tự từ trái qua phải. Có một đồng hồ nước đang nằm tại ô (y, x), dòng y cột x. Người ta muốn lát các ô còn lại trong sân bằng gạch hình chữ L kích thước 3 ô vuông (xem hình dưới, đồng hồ nước là ô (1,4)). Bạn hãy lập phương án để lát sân nhé.

Số ô vuông trong sân: n2 = 22k = 4k. Số ô cần lát: n2-1 = 4k - 1 = 3A với A là số viên gạch cần dùng.
Dữ liệu nhập:
- Là 3 số nguyên n, y, x cách nhau một khoảng trắng (2 ≤ n ≤ 256; 1 ≤ y, x ≤ n; n có dạng lũy thừa của 2).
Dữ liệu xuất:
- Nếu không có đáp án, in ra -1.
- Nếu có đáp án: dòng đầu tiên là số nguyên A biểu thị số viên gạch cần dùng.
Trong A dòng tiếp theo, mỗi dòng gồm 6 số nguyên Y1, X1, Y2, X2, Y3, X3, mỗi số cách nhau một khoảng trắng. 6 số nguyên trên biểu thị một viên gạch. (Y1, X1), (Y2, X2), (Y3, X3) là 3 ô của viên gạch.
Nếu có nhiều đáp án, in ra một đáp án bất kỳ. Trong một viên gạch thứ tự của 3 ô là không quan trọng, miễn là 3 ô ghép lại thành hình chữ L.
Ví dụ
input
4 1 4
output
5
1 1 1 2 2 1
1 3 2 3 2 4
2 2 3 2 3 3
3 1 4 1 4 2
4 3 4 4 3 4