白準1012号有機白菜
https://www.acmicpc.net/problem/1012
アイデア
最初は50 x 50グリッドの配列をあげて、配列の最初のセルから始めます.
array[i][j]が1なら虫の数+1、array[i+1][j]とarray[i][j+1]が2、0なら変わらず、1なら2を加えたいです.
また、arrayが1より大きい場合は虫の数を増やすのではなく、下と右*2を同じようにしようとします.
でもそうします.
この場合、左のものは初めて出会った1より少ないので、カウントが*2にならないことに気づきます.
したがって、カスタム関数を作成し、数が1の場合は0に設定し、左、右、上、下で1に移動して、セルで再び関数を実行します.
ハーモニー
なぜなら.
これにより、配列に含まれないセルも関数の影響を受けます.なぜなら、1が低く3つのセルが連続してある場合、配列に隣接しないセルはゼロになるからです.
つまり、上下に1マスを残して、すべて0にする必要があります.
最終コード
グローバル変数としてメモリを節約したいです.
Find関数は2つの整数変数を受け入れます.
関数内に再読み込みされた部分にarrayを変数に入れます.
その結果printfゲートに入る前に終了し,arrayのx値が配列の範囲を超えて爆発したのかもしれない.
他者コード
drestar 2のコードです
https://www.acmicpc.net/user/drestar2
ただし、行列のセルが1または0の場合は、if(==1)を書く必要のない方法を利用します.
char配列を利用してメモリを節約するなどの細かい点は私とは違います.
アイデア
最初は50 x 50グリッドの配列をあげて、配列の最初のセルから始めます.
array[i][j]が1なら虫の数+1、array[i+1][j]とarray[i][j+1]が2、0なら変わらず、1なら2を加えたいです.
また、arrayが1より大きい場合は虫の数を増やすのではなく、下と右*2を同じようにしようとします.
でもそうします.
この場合、左のものは初めて出会った1より少ないので、カウントが*2にならないことに気づきます.
したがって、カスタム関数を作成し、数が1の場合は0に設定し、左、右、上、下で1に移動して、セルで再び関数を実行します.
ハーモニー
#include <stdio.h>
void Find(int array[][50],int X, int Y)
{
array[X][Y] = 2;
if (array[X + 1][Y] == 1) Find(array, X + 1, Y);
if (array[X][Y + 1] == 1) Find(array, X, Y + 1);
if (array[X - 1][Y] == 1) Find(array, X - 1, Y);
if (array[X][Y - 1] == 1) Find(array, X, Y - 1);
}
int main()
{
int i, j, k, M, N, K, T ,X, Y;
scanf("%d", &T);
for (i = 0; i < T; i++)
{
int array[50][50] = { 0 };
int count = 0;
scanf("%d %d %d", &M, &N, &K);
for (j = 0; j < K; j++)
{
scanf("%d %d", &X, &Y);
array[X][Y] = 1;
}
for (j = 0; j < M; j++)
{
for (k = 0; k < N; k++)
{
if (array[j][k] == 1)
{
Find(array, j, k);
count++;
}
}
}
printf("%d\n", count);
}
return 0;
}
しかし、このようにしても間違いが発生します.なぜなら.
これにより、配列に含まれないセルも関数の影響を受けます.なぜなら、1が低く3つのセルが連続してある場合、配列に隣接しないセルはゼロになるからです.
つまり、上下に1マスを残して、すべて0にする必要があります.
最終コード
#include <stdio.h>
void Find(int array[][52], int X, int Y)
{
array[X][Y] = 2;
if (array[X + 1][Y] == 1) Find(array, X + 1, Y);
if (array[X][Y + 1] == 1) Find(array, X, Y + 1);
if (array[X - 1][Y] == 1) Find(array, X - 1, Y);
if (array[X][Y - 1] == 1) Find(array, X, Y - 1);
}
int main()
{
int i, j, k, M, N, K, T, X, Y;
scanf("%d", &T);
for (i = 0; i < T; i++)
{
int array[52][52] = { 0 };
int count = 0;
scanf("%d %d %d", &M, &N, &K);
for (j = 0; j < K; j++)
{
scanf("%d %d", &X, &Y);
array[X + 1][Y + 1] = 1;
}
for (j = 1; j <= M; j++)
{
for (k = 1; k <= N; k++)
{
if (array[j][k] == 1)
{
Find(array, j, k);
count++;
}
}
}
printf("%d\n", count);
}
return 0;
}
誤って作成されたコード#include <stdio.h>
int array[50][50];
void Find(int X, int Y)
{
array[X][Y] = 0;
if (array[X + 1][Y] == 1) Find(array, X + 1, Y);
if (array[X][Y + 1] == 1) Find(array, X, Y + 1);
if (array[X - 1][Y] == 1) Find(array, X - 1, Y);
if (array[X][Y - 1] == 1) Find(array, X, Y - 1);
}
int main()
{
int i, j, k, M, N, K, T, X, Y;
scanf("%d", &T);
for (i = 0; i < T; i++)
{
int count = 0;
scanf("%d %d %d", &M, &N, &K);
for (j = 0; j < K; j++)
{
scanf("%d %d", &X, &Y);
array[X][Y] = 1;
}
for (j = 0; j < M; j++)
{
for (k = 0; k < N; k++)
{
if (array[j][k] == 1)
{
Find(j, k);
count++;
}
}
}
printf("%d\n", count);
}
return 0;
}
コードを修正するときに非常にでたらめな間違いを犯した.グローバル変数としてメモリを節約したいです.
Find関数は2つの整数変数を受け入れます.
関数内に再読み込みされた部分にarrayを変数に入れます.
その結果printfゲートに入る前に終了し,arrayのx値が配列の範囲を超えて爆発したのかもしれない.
他者コード
drestar 2のコードです
https://www.acmicpc.net/user/drestar2
#include <stdio.h> // 처음에 메인 함수부터 읽어볼 것이다.
int dy[4] = {-1, 1, 0, 0};// 메인함수를 읽고 여기로 돌아왔다. dy dx가 뭘 의미하는걸까? 통상적인 의미로 생각하면 x와 y의 변화량인데
int dx[4] = { 0, 0,-1, 1};
void del(char a[][52], int y, int x) {
int i, y1, x1;
a[y][x]--; // a[y][x]는 일단 0 이 된다.
왜 y,x이냐 앞쪽이 행 뒤쪽이 열이므로 직관적으로 y값 x값이기 때문
for (i=0; i<4; i++) {
y1=y+dy[i], x1=x+dx[i]; //이렇게 코드의 길이를 줄이다니 참신하다.
if (a[y1][x1])
del(a, y1, x1);// 이동한 칸이 1일 때만 del실행
나랑 완벽히 같은 아이디어이나 구현이 조금 다르다.
}
}
int main() {
char a[52][52] = {0, };// 일단 char배열을 사용하여 메모리를 아꼈다.
int t, m, n, k, i, j, c;
scanf("%d", &t);
while (t--) { //테스트 케이스 개수만큼
c = 0; //내 코드의 카운트와 같은 역할
scanf("%d%d%d", &m, &n, &k);
while (k--) { //k는 다시 안 쓰니까 이렇게 써먹을 수 있다.
scanf("%d%d", &j, &i);
a[i+1][j+1]++;
}
for (i=1; i<=n; i++) {
for (j=1; j<=m; j++) {
if (a[i][j]) { //a배열의 그 칸의 수가 0이 아니면
del(a, i, j); //딜리트 함수 실행
c++; //c++, 아 이걸 보니 딜리트 함수는 인접한 칸들을 0으로 만들겠구나
}
}
}
printf("%d\n", c);
}
}
これはC言語の二等コードで、私と考えはほとんど同じです.ただし、行列のセルが1または0の場合は、if(==1)を書く必要のない方法を利用します.
char配列を利用してメモリを節約するなどの細かい点は私とは違います.
Reference
この問題について(白準1012号有機白菜), 我々は、より多くの情報をここで見つけました https://velog.io/@honeyricecake/백준-1012번-유기농-배추テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol