Shining...

/*문제 설명

n×n의 행렬로 지형도가 표시된 산이 있다.행렬의 원소의 값은 양의 정수 값으로 그 위치에서의 높이를 말해준다.등산가들은 산의 바깥지역(높이 0)으로부터 정상에 도달하기 위하여 가장 경제적인 루트를 탐색하려고 한다.경제적인 경로란 힘을 가장 적게 들이고 정상까지 올라갈 수 있는 길을 말한다.

예를 보면서 설명해보자.다음은 행렬 Mount[5, 5]로 표시된 산악지형이다.산의 정상은 Mount[3, 3]의 위치에 있으며, 그 높이는 6이다.그리고 이 산의 바깥지역은 모두 해발이 0이다.등산가가 산에 오르는 시작점의 위치는 산의 바깥지역의 어디에서 시작해도 좋다.

등산가는 어떤 한 지역에서 그 위치에 인접한 네 방향(위, 아래, 왼쪽, 오른쪽)으로만 움직일 수 있다.인접한 지역으로 움직일 수 있는 경우는(1) 평지로 이동할 경우, (2) 내려갈 경우, (3) 올라갈 경우의 세 가지이다.이 세 가지 경우에 필요한 "힘"의 양은 다음과 같이 표현될 수 있다.

(1)인접한 같은 높이의 지역을 수평 이동할 경우에는 그냥 평지를 걸어가면 되므로 힘이 전혀 들지 않는다고 가정한다.예를 들면 Mount[5, 2]에서 Mount[5, 3]으로 이동하는 경우와 Mount[4, 5]에서 Mount[5, 5]로 이동하는 경우에는 전혀 힘이 들지 않는다.

(2)내리막길을 따라갈 경우(예를 들면, Mount[2, 3]에서 Mount[2, 2]로 갈 때)에는 그 높이 차이만큼의 힘이 든다.즉 이 경우에는 5 - 3 = 2만큼의 힘이 든다.

(3)오르막길을 오를 경우에는 이동할 두 지역의 높이 차의 제곱만큼의 힘이 든다.즉 Mount[1, 2]에서 Mount[1, 3]으로 갈 경우는(4 - 2)2 = 4 만큼의 힘이 든다.

입력

첫째 줄에는 산의 크기인 Mount[n, n]의 n값이 주어지고, 두 번째 줄에는 정상의 위치 Mount[y, x]의 y, x값이 주어진다.

단, Mount[n, n]에서 n은 100이하이고, 각 지형의 최대 높이는 50이하라고 가정한다.

그 다음 n개의 줄은 산의 크기에 따른 각 지점의 높이가 양의 정수 값으로 주어진다.

출력

첫째 줄에 정상까지 도달하는 가장 경제적인 경로를 따라 올라가는데 사용된 힘을 출력한다.

입력 예시

5

3 3

1 2 4 3 2

1 3 5 4 4

2 3 6 5 1

3 1 4 1 3

2 3 3 5 3

출력 예시

8

도움말

경로는 다음과 같다.

2[1, 5]->3[1, 4]->4[2, 4]->5[3, 4]->6[3, 3]

= 2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 + 1 * 1

= 8

*/

#include<stdio.h>

/*

5

3 3

1 2 4 3 2

1 3 5 4 4

2 3 6 5 1

3 1 4 1 3

2 3 3 5 3

*/

int N;

int GARO, SERO;

int map[102][102];

int chk[102][102];

typedef struct {

int posY;

int posX;

} _pos;

_pos POSITION[1000000];

void main()

{

int i, j;

scanf("%d", &N);

scanf("%d %d", &SERO, &GARO);

for (i = 1; i <= N; i++)

{

for (j = 1; j <= N; j++)

{

scanf("%d", &map[i][j]);

}

}

for (i = 1; i <= N; i++)

{

for (j = 1; j <= N; j++)

{

chk[i][j] = 0x7fffffff;

}

}

int head = 0, tail = 0;

for (i = 0; i <= N +1; i++)

{

for (j = 0; j <= N +1; j++)

{

if (chk[i][j] == 0)

{

POSITION[tail].posY = i;

POSITION[tail].posX = j;

tail++;

}

}

}

int Dy[] = { -1, 1, 0, 0 };

int Dx[] = { 0, 0, -1, 1 };

int temp;

while (1)

{

if (head == tail) break;

for (int dir = 0; dir < 4; dir++)

{

int tmpY = POSITION[head].posY + Dy[dir];

int tmpX = POSITION[head].posX + Dx[dir];

if (tmpY >= 1 && tmpX >= 1 && tmpY <= N && tmpX <= N)

{

temp = map[POSITION[head].posY][POSITION[head].posX] - map[tmpY][tmpX];

if (temp < 0) temp = temp * temp;

temp += chk[POSITION[head].posY][POSITION[head].posX];

if (chk[tmpY][tmpX] > temp)

{

chk[tmpY][tmpX] = temp;

POSITION[tail].posY = tmpY;

POSITION[tail].posX = tmpX;

tail++;

}

}

}

head++;

}

printf("%d", chk[SERO][GARO]);

}

#include<stdio.h>

/*

덧셈을 못하는 철수를 공부시키기 위해 자연수들을 주고, 그 중에 몇 개의 수를 골라서 그 합이 K가 될 수 있는지 알아보라고 시켰다.

철수 어머니가 자연수들을 무작위로 선택해서 본인도 가능한지 아닌지 모르고 있다. 어머니가 채점을 할 수 있게 주어진 문제의 답을 찾아주자.

번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다.

두 번째 줄부터 아래 내용이 T개 만큼 주어진다.

첫 줄에 자연수 개수 N(5 <= N <= 20)과 K(1 <= K <= 2,000,000)가 공백으로 구분되어 입력된다.

다음 줄에 N개의 자연수 di(1 <= di <= 100,000)가 공백으로 구분되어 입력된다.

T줄에 걸쳐 각 테스트 케이스 별로 주어진 자연수 중 몇 개의 합이 K가 되면 “YES”를 아니면 “NO”를 출력한다.

입력 예시

2

5 19

1 2 4 7 10

5 25

1 2 4 7 10

출력 예시

YES

*/

#include<stdio.h>

int T;

int N;

int CNT;

int GOAL;

int num[100001];

int dfs(int pos, int cost)

{

if (cost > GOAL) return 0;

if (cost == GOAL) return 1;

for (int i = pos; i < N; i++) // 다중트리

{

if (dfs(i + 1, cost + num[i]) == 1) return 1;

}

return 0;

}

int dfs(int pos, int cost)

{

if (pos > cntN)  return 0;

if (cost > GOAL) return 0;

if (cost == GOAL) return 1;

if (dfs(pos + 1, cost + arr[pos]) == 1) return 1; // 이진트리

if ( dfs(pos + 1, cost )==1) return 1;

}

void main()

{

scanf("%d", &T);

while (T--)

{

scanf("%d %d", &N, &GOAL);

for (int i = 0; i < N; i++)

{

scanf("%d", &num[i]);

}

printf("%s\n", dfs(0, 0) == 1 ? "YES" : "NO");

}

}

#include<stdio.h>

typedef struct {

int sero;

int garo;

int idx;

int stat;

} _zergling;

하나로 모두 묶을 수 없기 때문에, 두가지를 동시에 사용해야 한다.

Zergling(가로,세로,idx)과 map(stat) 두개를 사용해서 처리

_zergling map[100][100];

_zergling Zergling[1000000];

int maps[100][100];

int cnt_time;

int Dx[] = { 0, 1, 0, -1 };

int Dy[] = { -1, 0, 1, 0 };

void main()

{

freopen("input.txt", "r", stdin);

int garo; int sero;

scanf("%d %d", &garo, &sero);

for (int i = 0; i < sero; i++)

{

for (int j = 0; j < garo; j++)

{

scanf("%1d", &map[i][j].stat);

maps[i][j] = map[i][j].stat;

if (map[i][j].stat == 1)

{

map[i][j].garo = j;

map[i][j].sero = i;

}

}

}

int zerg_garo = 0; 

int zerg_sero = 0;

scanf("%d %d", &zerg_garo, &zerg_sero);

int head = 0; int tail = 0;

map[zerg_sero - 1][zerg_garo - 1].stat = 0;

Zergling[tail].idx = 3;

Zergling[tail].garo = zerg_garo - 1;

Zergling[tail].sero = zerg_sero - 1;

cnt_time = map[zerg_sero - 1][zerg_garo - 1].idx;

tail++;

int a = 0;

while (1)

{

if (head == tail) break;

for (int dir = 0; dir < 4; dir++)

{

int garo_t = Zergling[head].garo + Dx[dir];

int sero_t = Zergling[head].sero + Dy[dir];

if (map[sero_t][garo_t].stat == 1)

{

a++;

map[sero_t][garo_t].stat = 0;

Zergling[tail].idx = Zergling[head].idx + 1;

Zergling[tail].garo = garo_t; // myqueue.push 의 다른 표현?

Zergling[tail].sero = sero_t;

cnt_time = (cnt_time > Zergling[tail].idx) ? cnt_time : Zergling[tail].idx;

tail++;

}

}

head++;

}

int cnt_num = 0;

for (int i = 0; i < sero; i++)

{

for (int j = 0; j < garo; j++)

{

scanf("%1d", &map[i][j].stat);

if (map[i][j].stat == 1)

{

cnt_num++;

}

}

}

printf("%d\n%d", Zergling[head - 1].idx, cnt_num);

}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=30&sfl=wr_subject

#include<stdio.h>

/*

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다.

이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이

몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면,

그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

efc6e5f9d670c6da62174cf11a66a8c2_1449731

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이

몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

[Copy] 5 7 3 0 2 4 4 1 1 2 5 4 0 6 2

[Copy] 3 1 7 13

*/

typedef struct {

int sX;

int sY;

int eX;

int eY;

} _pos;

_pos POS[1000];

int map[100][100] = { 0, };

int nCount = 0;

int nArea = 0;

int Area[100] = { 0, };

int sero;

int garo;

int idx = -1;

void find(int se, int ga)

{

nCount++;

if (se - 1 >= 0 && map[se - 1][ga] == 0) 

{

map[se - 1][ga] = idx;

find(se - 1, ga); 

}

if (se + 1 < sero && map[se + 1][ga] == 0)

{ 

map[se + 1][ga] = idx; 

find(se + 1, ga); 

}

if (ga - 1 >= 0 && map[se][ga - 1] == 0) 

{ 

map[se][ga - 1] = idx; 

find(se, ga - 1); 

}

if (ga + 1 < garo && map[se][ga + 1] == 0)

{ 

map[se][ga + 1] = idx;

find(se, ga + 1); 

}

//int Dy[] = { 1, 0,0, -1 };

//int Dx[] = { 0,-1, 1, 0 };

//nArea++;

//int head = 0;

//int tail = 1;

//while (1)

//{

// for (int x = 0; x < 4; x++)

// {

// int tmpX = garo + Dx[x];

// int tmpY = sero + Dy[x];

// if (map[tmpY][tmpX] == 0)

// {

// map[tmpY][tmpX] == -1;

// nCount++;

// }

// }

//}

}

void main()

{

int count;

// freopen("input.txt", "r", stdin);

scanf("%d %d %d", &sero, &garo, &count);

for (int i = 0; i < count; i++)

{

scanf("%d %d %d %d", &POS[i].sX, &POS[i].sY, &POS[i].eX, &POS[i].eY);

int tmpX = POS[i].eX - POS[i].sX;

int tmpY = POS[i].eY - POS[i].sY;

for (int y = POS[i].sY; y < tmpY + POS[i].sY; y++)

{

for (int x = POS[i].sX; x < tmpX + POS[i].sX; x++)

{

map[y][x]++;

}

}

}

for (int i = 0; i< sero; i++)

{

for (int j = 0; j < garo; j++)

{

if (map[i][j] == 0)

{

map[i][j] = --idx;

find(i, j);

Area[nArea++] = nCount;

nCount = 0;

}

}

}

for (int i = 0; i < nArea-1; i++)

{

for (int j = 0; j < nArea - 1 -i; j++)

{

if (Area[j] > Area[j + 1])

{

int tmp = Area[j];

Area[j] = Area[j + 1];

Area[j + 1] = tmp;

}

}

}

printf("%d\n", nArea);

for (int i = 0; i < nArea; i++)

{

printf("%d ", Area[i]);

}

}

BFS 

   소수경로 공부하기

   해밍경로

   경로 찾기 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1522&sca=3040)

   소수와 함께 하는 여행(http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=615&sca=3040)

   효율적인 해킹

   저글링 방사능 오염 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358%20&sca=3040)

백트래킹 

   해밀턴 순환회로(http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030#none)

   치즈 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=3030)

   영역구하기(6/14 완료)

최단거리

   등산로찾기 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=391&sca=3070#none

What question do you hate to answer?

I hate to answer the question about my religion. Sometimes I find people who think depending on the religion. So I don't want to answer.

3/28

What kinds of challenge would you like take on? Why?

I've always wanted to develop games! I really love to play games, but despite being a software engineer, I've only developed lots of test software.

3/29

Is there someone you admire? Why or why not?

I really admire my grandfather for his knowledge, because he was really smart as a doctor. Sometimes, I am astonished he can speak three languages fluently.

3/30

Are you a traveler? Why or why not?

I'm a born traveler. My father told me that I need to go abroad and study lots of things. Unfortunately, recently, I haven't had enough time.

3/31

Recall a memorable day in your life.

I remember the day when I passed my employment exam. I didn't expected to pass the exam because it was really hard. I'll never forget that day!

4/1

What was your biggest mistake?

It was the day when I broke my dad's computer. I just wanted to play a game, I didn't doubt the PC as infected with a virus. Finally, my dad spanked me.

4/4

What do you do when you can't fall asleep?

I usually think of a pleasant memory of something I've experienced. I often think about these kinds of memories because I believe they help me to fall asleep.

4/5

When do you feel the generation gap the most?

I feel the generation gap when a specific song which I have never heard becomes popular. I also don't want to be behind the trend, but I have no time to listen!

4/6

If you had only 24 hours to live, what would you do?

I would spend it with my friends and family, and I would recall the memories in which I was with my friends.

4/7

What is more important, seniority or experience?

In my case experience is more important. Being a engineer, Seniority doesn't help me to develop well made software.

4/8

Are you a religious person?

I'm not a religious person. I used to be religious but now I'm an atheist. Being an engineer, I've started to believe that everything is based on probability.

4/11

If you could be invisible for a day what would you do and why?

If I could be invisible, I would want to modify university score, and them I could join a really good company such as Google.

4/12

What superstitions do you know of?

There're lots of people who believe superstitions. For example, if a boyfriend would give shoes to his girlfriend, they would break up.

4/13

What makes you cringe?

When I found a letter I wrote when I was young, it made me cringe. I think cringing sometimes, can make me happy.

4/14

Are you good at throwing old things away?

I can't throw away things. so my wife really hates my habit. I think all kinds of thins have their own memory so I can't throw them away.

4/15

What;s unforgivable? Why?

I won't be able to forgive someone who lies to me on a regular basis at work. I really hate these kinds of people, and I can't understand why they lie.

4/18

How do you manage yourself when you're angry?

I'm good at relieving my anger, so I don't have to go outside and find a place where I can let it out. Through meditation I can clear my mind.

4/19

If you could change one physical feature of yourself, what would it be and why?

I've always wanted to change my hair. These days, my head looks bald. So sometimes, my daughter asks me if she would become bald.

4/20

Do you think you're fashionable?

I'm not fashionable. But my wife is fashionable. She loves to make me a fashionable person. Sometimes, I'd get complement by friends. I give thanks to her.

4/21

Do you think it's important to get along with the parents of your significant other?

Of course. I also love my mother-in-law. I always thank her. My wife also thinks this is a good scene to see.

4/22

What question do you hate to answer?

I hate to answer the question about my religion. Sometimes I find people who think depending on the religion. So I don't want to answer.

4/25

What's the hardest thing you've ever done?

The hardest thing I've ever done was earning money when I was a university student because my father's company wen bankrupt.

4/26

When was a time that you felt very proud?

I feel proud every year because my salary goes higher. I think it is not easy to get an increase every year.

4/27

What is something that you hate doing, but you do it anyway?

I hate people who bother me. When I need to concentrate on my work and people interrupt me, I can't stand it.

4/28

Are first impression important? Why?

I agree that first impression are important. For example, an annoying person is rare, but if I meet someone who is annoying then I can know a lot about that person.

4/29

Would you ever get a tattoo? If yes, what kinds of tattoo would you get?

I don't want to get a tattoo. There are lots of thing that would remind me of my past, not only a tattoo. Furthermore, I do not like painful things!

5/2

What hobbies did you take up recently but have given up?

I've taken up playing the violin. I've always wanted to play the violin. But being an employee, I don't have enough time to play. So I gave up playing the violin.

5/3

What makes you laugh? Why?

Watching my kids makes me laugh. Despite them fighting sometimes, they are really cute. I'm very proud of them. Looking at their photos also makes me laugh.

5/4

Is it necessary to get your parents' approval for marriage?

I don't think it's necessary because the decision to get married is made between the two people getting married. We don't need to be concerned for their life.

5/5

Do you have any morning rituals?

When I get up in the morning, the first thing I do is planning my schedule for the day. By writing notes, I can finish my work completely.

5/6

Tell me about a time you had to let go of you pride.

When I fought with my coworker, we didn't talk after that. I thought the problem was made by my coworker. But in face, it wasn't caused by him. So apologized.

5/9

Do you prefer to blend in or stand out?

I tend to stand out. Sometimes I can see many people who don't want to participate in some programs. In this case, I stand out and make a decision.

5/10

What is a good way to discipline children?

I think there isn't a solution to discipline children. Every parent and child don't want to hurt each other. Too much spanking is also not good.

5/11

Which is worse: failing or never trying?

I think never trying is worse than failing. Sometimes we could regret never trying. At least I can not ignore this kind of feeling.

5/12

What's the most recent compliment you've given to someone?

I gave a compliment to a coworker who came from the Xian R&D Center about his diligence. Because he finished our project completely. We're so proud of him.

5/13

Have you ever pretended to know something that you don't actually know?

Sometimes I pretend to know something. Because I need to persuade someone. Sometimes I have to pretend to know something. Otherwise my boss would be upset.

5/16

Do you believe vitamins and supplements makes you healthier?

Yes, I do. Being an engineer, sometimes I have to work all night. Due to intake of enough vitamins, I can see the code on the monitor. So I need them!

5/17

What do you like about this Band? Why?

To be honest, except this program(English teaching) there isn't any reason why I have to use this application. Because I'm already familiar with Kakaotalk.

5/18

What's a New Year's resolution that you have actually kept?

Actually, studying Chinese was one of my resolutions. But I don't have enough time to study Chinese day by day. I gave up this year's resolutions.

5/19

What was the last good deed you did?

I think it would have to be teaching an IT class. Through teaching a multicultural family, I can feel happiness because there's someone I can help.

5/20

Is it necessary to send your child to university?

기본적으로 이 문제는 두가지 방법으로 구할 수 있다.

1) 일단 L의 위치들을 다른곳에 각자 구한뒤 위치 차이 중 최대값으로 구할 것이냐

2) 각위치에서 가장 멀리 떨어져있는 애들의 위치 중 최대값으로 구할 것이냐

금번엔 2번으로 구했지만 1번으로 구해보고 싶음.

#include<stdio.h>

#include<memory.h>

/*

5 7

WLLWWWL

LLLWLLL

LWLWLWW

LWLWLLL

WLLWLWW

*/

char map[50][50];

int visited[50][50] = { 0 };

int max = 0;

int distance = 0;

int N, M;

typedef struct {

int row;

int col;

} _position;

_position point[2500];

int Dy[4] = { -1, 0, 1, 0 };

int Dx[4] = { 0, -1, 0, 1 };

int bfs(int row, int col)

{

int head, tail;

int max;

int i;

int tmp_row, tmp_col;

max = -1;

head = 0;

tail = 0;

memset(visited, -1, sizeof(visited)); // memory.h 나 string.h 를 못쓸때는 강제for문으로 변경해줘야함

memset(point, -1, sizeof(point)); // memory.h 나 string.h 를 못쓸때는 강제for문으로 변경해줘야함

point[tail].row = row;

point[tail].col = col;

visited[row][col] = 0;

tail++;

while (1)

{

if (head == tail) break;

for (i = 0; i < 4; i++) // 상 하 좌 우 

{

tmp_row = point[head].row + Dy[i];

tmp_col = point[head].col + Dx[i];

if (tmp_row >= 0 && tmp_row < N && tmp_col >= 0 && tmp_col < M) // MAP 범위 안에 존재

{

if (visited[tmp_row][tmp_col] == -1 && map[tmp_row][tmp_col] == 'L')

{

point[tail].row = tmp_row;

point[tail].col = tmp_col;

tail++;

visited[tmp_row][tmp_col] = visited[point[head].row][point[head].col] + 1; // 이전 위치보다 1칸 더 갔다는 뜻

// visited[tmp_row][tmp_col] = visited[tmp_row-Dy[i]][tmp_col-Dx[i]] + 1; 로 생각하는 게 더편함

if (visited[tmp_row][tmp_col] > max)

{

max = visited[tmp_row][tmp_col];

}

}

}

}

head++;

}

return max;

}

int main()

{

int i, j, k;

scanf("%d %d", &N, &M);

for (i = 0; i < N; i++)

{

scanf("%s", map[i]);

}

for (i = 0; i < N; i++)

{

for (j = 0; j < M; j++)

{

if (map[i][j] == 'L')

{

distance = bfs(i, j);

if (distance > max)

{

max = distance;

}

}

}

}

printf("%d\n", max);

}

//1번으로 구하는 것은 아래와 같음

//typedef struct {

// int sero;

// int garo;

//} _land;

//_land LAND[2500];

//_land POINT[250000];

//char map[50][50];

//int visited[50][50] = { 0, };

//

//int bfs(_land x, _land y)

//{

// memset(visited, -1, sizeof(visited));

// memset(POINT, -1, sizeof(POINT));

// int distance = 0;

// int head = 0;

// int tail = 0;

//

// int Dy[] = { -1,0,0,1 };

// int Dx[] = { 0 , -1, 1, 0 };

// int count = 0;

// while (head <= tail)

// {

// for (int i = 0; i < 4; i++)

// {

// int tmp_garo = Dx[i] + x.garo;

// int tmp_sero = Dy[i] + y.garo;

//

// if (tmp_sero == y.sero && tmp_garo == y.garo)

// {

// return count;

// }

// if (visited[tmp_sero][tmp_garo] == -1 && map[tmp_sero][tmp_garo] == 'L')

// {

// POINT[tail].garo = tmp_garo;

// POINT[tail].sero = tmp_sero;

// count++;

// tail++;

// }

// }

// head++;

// }

//

//}

//int main()

//{

// int sero;

// int garo;

//

//

// scanf("%d %d", &sero, &garo);

//

// for (int i = 0; i < sero; i++)

// {

// scanf("%s", map[i]);

// }

//

// // L의 위치 구하고, 배열에 넣기

// int idx = 0;

// for (int i = 0; i < sero; i++)

// {

// for (int j = 0; j < garo; j++)

// {

// if (map[i][j] == 'L')

// {

// LAND[idx].sero = i;

// LAND[idx].garo = j;

// idx++;

// }

// }

// }

// int max = 0; 

// int tmp = 0;

// // 이미 가로 세로 위치 구한 애들이고 L들로 구성된 애들임.

// for (int i = 0; i < idx; i++)

// {

// for (int j = 1; j < idx - 1; j++)

// {

// tmp = bfs(LAND[i], LAND[j]);

// if (max < tmp)

// {

// max = tmp;

// }

// }

// }

// printf("%d", max);

//}

/*

N×M장기판에 졸 한개와 말 한개가 놓여 있다.말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다.

말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자.

첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다.(1≤N, M≤100)

둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다.

단, 장기판의 제일 왼쪽 위의 위치가(1, 1)이다.

각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다.

말이 졸을 잡기 위한 최소 이동 횟수를 출력한다.

[Copy]

9 9

3 5 2 8

[Copy]

2

*/

#include <stdio.h>

typedef struct {

int sero;

int garo;

int idx;

} _position;

_position POSITION[1000000];

int  main()

{

int garo = 0; // 세로

int sero = 0; // 가로

int mal_sero = 0; // 말의 세로

int mal_garo = 0; // 말의 가로

int jol_sero = 0;

int jol_garo = 0;

scanf("%d %d", &sero, &garo);

scanf("%d %d", &mal_sero, &mal_garo);

scanf("%d %d", &jol_sero, &jol_garo);

int head = 0;

int tail = 1;

int Dy[] = { 2, 1, -1, -2, 2, 1, -1, -2 };

int Dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

int map[102][102] = { 0, };

int tmp_sero = 0;

int tmp_garo = 0;

POSITION[0].sero = mal_sero;

POSITION[0].garo = mal_garo;

POSITION[0].idx = 0;

while (1)

{

for (int i = 0; i < 8; i++)

{

tmp_sero = POSITION[head].sero + Dy[i];

tmp_garo = POSITION[head].garo + Dx[i];

if (tmp_sero >= 1 && tmp_sero <= sero && tmp_garo >= 1 && tmp_garo <= garo)

{

if (map[tmp_sero][tmp_garo] == 0)

{

if (tmp_garo == jol_garo && tmp_sero == jol_sero)

{

printf("%d\n", POSITION[head].idx + 1);

return 0;

}

POSITION[tail].sero = tmp_sero;

POSITION[tail].garo = tmp_garo;

POSITION[tail].idx = POSITION[head].idx + 1;

tail++;

map[tmp_sero][tmp_garo] = 1;

}

}

}

head++;

}

return 0;

}

#include <iostream>

/*

입력 파일의 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.

세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례 로 입력 파일의 둘째 줄부터 마지막 줄까지 주어진다.

치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어 지며 각 숫자 사이에는 빈칸이 하나씩 있다.

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출 력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

*/

//int M, N;

//int map[100][100];

//

//int time;

//int cnt_lastcheese;

//int cnt[100];

//void fill(int x, int y)

//{

// // 공기와 접촉된 칸만 녹임

// // c를 찾기

// if (x - 1 > 0) fill(x - 1, y);

// if (x + 1 < N) fill(x + 1, y);

// if (y - 1 > 0) fill(x, y - 1);

// if (y + 1 < N) fill(x, y + 1);

//}

//

//void main()

//{

// freopen("input.txt", "r", stdin);

// setbuf(stdout, NULL);

// scanf("%d %d", &M, &N);

// for (int i = 0; i < M; i++)

// {

// for (int j = 0; j < N; j++)

// {

// scanf("%d", &map[i][j]);

// if (map[i][j] == 1)

// {

// cnt[0]++;

// }

// }

// }

//

// //밖을 채우기

// fill();

// printf("%d", time);

// printf("%d", cnt_lastcheese);

//}

/*

1840 치즈 BFS로 풀기   정올 / 알고리즘

2012.08.05. 23:16

복사http ://blog.naver.com/hero1014/20163651496

번역하기

전용뷰어 보기

치즈

Time Limit : 1000MS

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색 으로 표시된 부분)가 놓여 있다.판의 가장자리(<그림 1>에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다.치 즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모 두 녹아 없어진다.그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모 두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 를 구하는 프로그램을 작성하시오.

입력 파일의 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.세로와 가로의 길이는 최대 100이다.판의 각 가로줄의 모양이 윗 줄부터 차례 로 입력 파일의 둘째 줄부터 마지막 줄까지 주어진다.치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어 지며 각 숫자 사이에는 빈칸이 하나씩 있다.

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출 력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

13 12

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 1 0 0 0

0 1 1 1 0 0 0 1 1 0 0 0

0 1 1 1 1 1 1 0 0 0 0 0

0 1 1 1 1 1 0 1 1 0 0 0

0 1 1 1 1 0 0 1 1 0 0 0

0 0 1 1 0 0 0 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

3

5

*/

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

ifstream in("input.txt");

ofstream out("output.txt");

int min = 999;

int map[101][101] = { 0, };//치즈의 위치 입력 받기 위한 2차원 배열 

int tx[4000], ty[4000];//큐  3000은 작음 

int x[4] = { 0,0,1,-1 };

int y[4] = { 1,-1,0,0 };

int i, j;

int se, ga;//세로 가로의 길이 

in >> se >> ga;// input 첫째줄의 세로 가로길이 

for (i = 1; i <= se; i++)//세로 읽기

for (j = 1; j <= ga; j++)//가로 읽기

in >> map[i][j];//

int f = 1, s = 1;

tx[f] = 1;//큐 초기값 

ty[f] = 1;

int tempx, tempy;

int k;

int cnt;

for (cnt = 0;; cnt++)//치즈가 모두 녹아서 없어지는 데 걸리는 시간

{

f = 1; s = 1;

while (f <= s)// f,s 좌표를 중심으로 하상우좌 순서로 스캔 >> 스캔값 0이면 -1 그리고  >>s는 0의 갯수

{

printf("처음 while 시작 : f = %d , s = %d\n", f, s);

for (i = 0; i<4; i++)

{

tempx = tx[f] + x[i];// tx[1] + {0 0 1 -1}

tempy = ty[f] + y[i];// tx[1] + {1 -1 0 0} 

printf("\tif문 : i  = %d// tempx= %d ,  tempy =%d \n", i, tempx, tempy);

if (tempx > 0 && tempx <= se && tempy <= ga && tempy>0 && map[tempx][tempy] == 0)

{

s++;

tx[s] = tempx;

ty[s] = tempy;

map[tempx][tempy] = -1;//이미 읽은 큐는 -1로 바꿔줌

printf("\t****s증가 : %d //map[%d][%d]=0 ////%d\n", s, tempx, tempy, map[tempx][tempy]);

}

}

f++;

printf("f 증가 : %d ", f);

}

int q, l;

k = 0;

for (q = 1; q <= se; q++)//세로 서치

for (l = 1; l <= ga; l++)//가로 서치

{

if (map[q][l] == 1)//치즈 1인 값 찾음

{

f = 1, s = 1;

while (f <= s)

{

for (i = 0; i<4; i++)

{

tempx = q + x[i];

tempy = l + y[i];

if (tempx > 0 && tempx <= se && tempy <= ga && tempy > 0 && map[tempx][tempy] == -1)

{ 

map[q][l] = 0;

k++;

break;

}

}

f++;

}

}

}

if (k>0 && k<min)

min = k;

int m = 0;

int n = 0;

for (q = 1; q <= se; q++)

{

for (l = 1; l <= ga; l++)

{

if (map[q][l] == -1)

{

m++;

map[q][l] = 0;

}

}

if (m == (se*ga))

n = 1;

}

if (n == 1)

break;

}

out << cnt;//치즈가 모두 녹아서 없어지는 데 걸리는 시간

out << endl;//다음줄

out << min;//모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수

printf("%d , %d", cnt, min);

return 0;

}

토마토 (고)

#include <stdio.h>

#include <stdlib.h>

int M, N;

int map[1000][1000];

typedef struct {

int row;

int col;

int day;

} _COORDI;

int head = 0, tail = 0;

_COORDI point[1000000];

int Dy[4] = { -1,1,0,0 };

int Dx[4] = { 0,0,-1,1 };

int min = 0;

int bfs(int row, int col)

{

int i;

int row_t, col_t;

while (1)

{

if (head == tail) break;

for (i = 0; i < 4; i++)

{

row_t = point[head].row + Dy[i];

col_t = point[head].col + Dx[i];

if (row_t >= 0 && row_t < N && col_t >= 0 && col_t < M)

{

if (map[row_t][col_t] == 0)

{

map[row_t][col_t] = 1;

point[tail].row = row_t;

point[tail].col = col_t;

point[tail].day = point[head].day + 1;

tail++;

}

}

}

head++;

}

return point[head - 1].day;

}

int main(int argv, char** argc) {

freopen("input.txt", "r", stdin);

setbuf(stdout, NULL);

scanf("%d %d", &M, &N);

for (int i = 0; i < N; i++)

{

for (int j = 0; j < M; j++)

{

scanf("%d", &map[i][j]);

if (map[i][j] == 1)

{

point[tail].row = i;

point[tail].col = j;

point[tail].day = 0;

tail++;

}

}

}

if (tail == 0)

{

printf("-1\n");

return 0;

}

if (tail == M * N)

{

printf("0\n");

return 0;

}

min = bfs(0, 0);

int find = 0;

for (int i = 0; i < N; i++)

{

for (int j = 0; j < M; j++)

{

if (map[i][j] == 0)

{

find = 1;

break;

}

}

}

if (find == 1)

{

printf("-1\n");

}

else

{

printf("%d\n", min);

}

return 0;//정상종료시 반드시 0을 리턴해야합니다.

}