ガチホ〇撲滅教

人の行く裏に道あり花の山

そろそろリハビリ終了かなAOJ【0509】

今日は、リハビリも進んできたので正答率の低い問題を解く事にした

AOJ【0509】シート(シート | Aizu Online Judge)

 

javaを用いての実装をすることにしたがここで使用しようと考えたのがPolygonクラス。

ポリゴンといえばポケモンだが、こいつはまさにそれ。カクカクの多角形を表現するのにはこいつが最適。こんなクラスまで用意しとうとかjava最強かよww

しかし、実際に今回のプログラミングで使用したのは、配列だ。

また、頭悪い発見をした。仕組みについてであるが以下の考え方で記述する。

 

まぁ、俺の中でのjavaは便利で理解しやすいが故、誰でもできそうという烙印が押されてしまいそうな言語という認識なのでいつかは、javaからの脱却をしなければならない??のだろうか笑

 

さて、問題 

 

〜考え方〜

1×1の正方形を以下のような配列でデータを格納し、各配列を正方形として処理、そしてセルの値が1ならばその領域はactiveであり、正方形がその領域に存在していると見なす。0であるならばその領域には正方形がないと考える。

この処理により、面積は瞬殺で出す事ができる。

 

面積?アクティブセルの数を数えるだけ。

まさに、瞬殺。

周の長さにおいても、一つの正方形につき4である。

しかし、4辺のうち他の正方形と接しているのでそのぶんを引かなくてはならないのだが

実は、これもある正方形の周の長さは、その対象としている正方形に

接している正方形の数だけ4から引いていけばよい。

 

[0][9] [1][9] [2][9] [3][9] [4][9] [5][9] [6][9] [7][9] [8][9] [9][9]
[0][8] [1][8] [2][8] [3][8] [4][8] [5][8] [6][8] [7][8] [8][8] [9][8]
[0][7] [1][7] [2][7] [3][7] [4][7] [5][7] [6][7] [7][7] [8][7] [9][7]
[0][6] [1][6] [2][6] [3][6] [4][6] [5][6] [6][6] [7][6] [8][6] [9][6]
[0][5] [1][5] [2][5] [3][5] [4][5] [5][5] [6][5] [7][5] [8][5] [9][5]
[0][4] [1][4] [2][4] [3][4] [4][4] [5][4] [6][4] [7][4] [8][4] [9][4]
[0][3] [1][3] [2][3] [3][3] [4][3] [5][3] [6][3] [7][3] [8][3] [9][3]
[0][2] [1][2] [2][2] [3][2] [4][2] [5][2] [6][2] [7][2] [8][2] [9][2]
[0][1] [1][1] [2][1] [3][1] [4][1] [5][1] [6][1] [7][1] [8][1] [9][1]
[0][0] [1][0] [2][0] [3][0] [4][0] [5][0] [6][0] [7][0] [8][0] [9][0]

 正方形の実装のイメージ図 

 

[0][9] [1][9] [2][9] [3][9] [4][9] [5][9] [6][9] [7][9] [8][9] [9][9]
[0][8] [1][8] [2][8] [3][8] [4][8] [5][8] [6][8] [7][8] [8][8] [9][8]
[0][7] [1][7] [2][7] [3][7] [4][7] [5][7] [6][7] [7][7] [8][7] [9][7]
[0][6] [1][6] [2][6] [3][6] [4][6] [5][6] [6][6] [7][6] [8][6] [9][6]
[0][5] [1][5] [2][5] [3][5] [4][5] [5][5] [6][5] [7][5] [8][5] [9][5]
[0][4] [1][4] [2][4] [3][4] [4][4] [5][4] [6][4] [7][4] [8][4] [9][4]
[0][3] [1][3] [2][3] [3][3] [4][3] [5][3] [6][3] [7][3] [8][3] [9][3]
[0][2] [1][2] [2][2] [3][2] [4][2] [5][2] [6][2] [7][2] [8][2] [9][2]
[0][1] [1][1] [2][1] [3][1] [4][1] [5][1] [6][1] [7][1] [8][1] [9][1]
[0][0] [1][0] [2][0] [3][0] [4][0] [5][0] [6][0] [7][0] [8][0] [9][0]

入力例1の図形の図

 緑色はアクティブセル(正方形が存在する)って感じで正方形を表現する。

 

以下コード

 

~FileRead_0509.java~

 

package sheets_0509;

 

import java.io.BufferedReader;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;

import java.util.ArrayList;

 

public class FileRead_0509 {

private ArrayList<Integer> sl = new ArrayList<Integer>();

private int sq = new int[100][100][10];

 

/**

* @return the sq

*/

public int getSq() {

returnsq;

}

 

/**

* @return the sl

*/

public ArrayList<Integer> getSl() {

returnsl;

}

 

/**

* 配列の初期化のメソッド

*/

public void initSq(){

for(int l = 0; l < 10; l++){

for(int i = 0; i < 100; i++){

for(int k = 0; k < 100; k++){

sq[i][k][l] = 0;

}

}

}

}

 

public int FileRead(String filename){

FileReader fr = null;

    BufferedReader br = null;

    try {

        fr = new FileReader(filename);

        br = new BufferedReader(fr);

       

        String line;

        int i;

        int count = 0;

 

        while((line = br.readLine()) != null){ //1行読む

        String word = line.split(" ", 0);

        i = Integer.parseInt(word[0]); //数字に変換

        sl.add(Integer.parseInt(word[1]));

                

        if(i == 0) break; //EoFとしての0がきたらメソッド終了

        for(int k = 0; k < i; k++){

        line = br.readLine();

        String w = line.split(" ", 0);

        int m, n;

        for(m = Integer.parseInt(w[0]); m < Integer.parseInt(w[2]); m++){

        for(n = Integer.parseInt(w[1]); n < Integer.parseInt(w[3]); n++){

        sq[m][n][count] = 1;

        }

        }

        }

        count++;

        }

    } catch (FileNotFoundException e) {

        e.printStackTrace();

    } catch (IOException e) {

        e.printStackTrace();

    } finally {

        try {

            br.close();

            fr.close();

        } catch (IOException e) {

            e.printStackTrace();

        }

    }

returnsq;

}

}

 

~sheets.java~

 

package sheets_0509;

 

public class Sheets {

private static FileRead_0509 file = new FileRead_0509();

private static int sq = new int[100][100][10];

 

public int square(int i){

int s = 0;

for(int m = 0; m < 100; m++){

for(int n = 0; n < 100; n++){

if(sq[m][n][i] == 1){

s++;

}

}

}

returns;

}

 

public int length(int i){

int l = 0;

for(int m = 0; m < 100; m++){

for(int n = 0; n < 100; n++){

if(sq[m][n][i] == 1){

l += 4;

//周りにアクティブセルが存在するかの確認

 

/**

* 左端を見るとき

*/

 

if(m == 0){

if(n == 0){ //左下端のとき

if(sq[m+1][n][i] == 1)

l--;

if(sq[m][n+1][i] == 1)

l--;

continue;

}

if(n == 100-1){ //左上端のとき

if(sq[m+1][n][i] == 1)

l--;

if(sq[m][n+1][i] == 1)

l--;

continue;

}

if(sq[m+1][n][i] == 1)

l--;

if(sq[m][n+1][i] == 1)

l--;

if(sq[m][n-1][i] == 1)

l--;

continue;

}

 

/**

* 右端を見るとき

*/

 

if(m == 100-1){

if(n == 0){ //右下端のとき

if(sq[m-1][n][i] == 1)

l--;

if(sq[m][n+1][i] == 1)

l--;

continue;

}

if(n == 100-1){ //右上端のとき

if(sq[m-1][n][i] == 1)

l--;

if(sq[m][n-1][i] == 1)

l--;

continue;

}

if(sq[m-1][n][i] == 1)

l--;

if(sq[m][n+1][i] == 1)

l--;

if(sq[m][n-1][i] == 1)

l--;

continue;

}

 

/**

* 下端を見るとき

*/

 

if(n == 0){

if(sq[m-1][n][i] == 1)

l--;

if(sq[m+1][n][i] == 1)

l--;

if(sq[m][n+1][i] == 1)

l--;

continue;

}

/**

* 上端を見るとき

*/

 

if(n == 100-1){

if(sq[m-1][n][i] == 1)

l--;

if(sq[m][n+1][i] == 1)

l--;

if(sq[m][n-1][i] == 1)

l--;

continue;

}

/**

* 端以外を見るとき

*/

if(sq[m-1][n][i] == 1)

l--;

if(sq[m+1][n][i] == 1)

l--;

if(sq[m][n-1][i] == 1)

l--;

if(sq[m][n+1][i] == 1)

l--;

}

}

}

returnl;

}

 

public void showAnswer(){

for(int i = 0; i < file.getSl().size(); i++){

if(file.getSl().get(i) == 1){

System.out.println(square(i));

}

if(file.getSl().get(i) == 2){

System.out.println(square(i));

System.out.println(length(i));

}

}

}

 

public static void main(String args[]){

Sheets sheets = new Sheets();

file.FileRead(args[0]);

sq = file.getSq();

sheets.showAnswer();

}

}

 

最後の方が脳筋のゴリラプログラムになってしまったが

処理方法が他になさそうなのであまり気にしない事にする笑