수다닷컴

알고리즘 명세를 했는데 뜻대로 작동안하네요.술에 취한 발퀴벌레가 nXm크기의 직사각형 방중간의 한타일위에 있다. 바퀴벌레는 임의로 타일에서 타일로 걸어간다. 바퀴벌레가 현재 타일에서 그 주위8개의 타일(벽 옆에 있지 않은 경우) 위로 같은 확률을 가지고 움직인다고 가정하자. 이때 적어도 한 번씩 방의 모든 타일을 지나는데 걸리는 시간은 얼마인가?

nXm배열 count는 방에서 바퀴벌레가 각 타일을 방문하는 횟수를 나타내는데 사용된다. 이배열의 모든 원소의 초기 값은 0이다. 방ㅇ에서 바퀴벌레의 위치는 좌표 (ibug,jbug)로 나타낸다. 바퀴벌레의 여덟가지 가능한 이동은 타일들의 위치, 즉 (ibug+imove[k],jbug+jmove[k])로 나타내며, 여기서 k는 0=k=7이고 imove와 jmove는 다음과 같다.
imove[0]=-1 jmove[0]=1
imove[1]=0 jmove[1]=1
imove[2]=1jmove[2]=1
imove[3]=1 jmove[3]=0
imove[4]=1 jmove[4]=-1
imove[5]=0 jmove[5]=-1
imove[6]=-1 jmove[6]=-1
imove[7]=-1 jmove[7]=0

주어진 정방의 8개 타일 중 어느 하나의 임의의 움직임은 0과 7사이의 어는 한 값 k를 생성함으로써 시뮬레이션 할 수 있다. 물론 바퀴벌레는 방 밖으로 벗어나 움직일수 없다. 벽위로 움직이는 좌표는 무시되어야 하고 새로운 임의 조합에 의해 움직임이 형성된다. 한 타일에 들어 갈때 마다 해당하는 배열 값이 증가되며, 이것은 지금까지 바퀴벌레가 그 타일을 방문한 횟수를 나타낸다. 모든 타일에 적어도 한번은 들어 왔을때 그 실험은 종료된다.
(a)2 n=40, 2=m20에 대해, m과 n의 모든 값을 처리한다

(b)다음 두경우, (1)n=15,m=15,시작점 (10,10)rhk (2) = n=39, m=19, 시작점 (1,1)에 대하여 실험하라

(c)반복 실행의 한계를 결정하라. 즉, 실험 중 바퀴벌레가 들어갈 수 잇는 타일의 수의 최대 값을 정하라. 이가정은 프로그램이 종료될 수 있도록 하기 위한 목적이다. 이문제에서는 최대 50000으로 결정하는 것이 적당하다.
Olson이 제공한 문제이다.질문 내용 : 40.19 대입후 1,1 좌표에서 50000이 넘는 이유를 모르겠어요.

#include stdio.h
#include stdlib.h
#include time.h
#include malloc.h
#define randomize() srand((unsigned)time(NULL))
typedef enum { FALSE, TRUE } BOOL;
#define M 19
#define N 40

int **matrix_alloc(int rows, int cols)
{
int i;
int **matrix;
matrix = (int **)malloc( sizeof(int *)*rows );
matrix[0] = (int *)malloc( sizeof(int)*rows*cols);
for(i=1; i rows; i++) matrix[i] = matrix[i-1] + cols;
return matrix;
}
void matrix_free(int **matrix)
{
if(matrix) {
if(matrix[0]) free(matrix[0]);
free(matrix);
}
}

int board[M][N] = { 0 };
BOOL check();
int main(){
int cm=0;
int cn=0;
printf(n의 크기\n);
scanf(%d,&cn);
printf(m의 크기\n);
scanf(%d,&cm);
int **board;
board = matrix_alloc(cm,cn); //-----배열 내용을 모두 0로 초기화 하고 싶어요,. 혹시 쓰레기 내용 생성그런가요?

int imove[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int jmove[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };
int count = 0;
int ibug, jbug, i_temp, j_temp;
int i, j, k;
printf(start i point(1 - %d) : , cn-2 );
scanf(%d, &ibug);
printf(start j point(1 - %d) : , cm-2 );
scanf(%d, &jbug);
board[--ibug][--jbug] = 1;
randomize();
while ( count 50000 ) {
if ( check() )
break;
k = rand()%8;
i_temp = ibug + imove[k];
j_temp = jbug + jmove[k];
if ( ( i_temp = 0 && i_temp cm ) &&
(j_temp = 0 && j_temp cn ) ) {
ibug = i_temp;
jbug = j_temp;
count++;
board[ibug][jbug]++;
}

}
for ( i = 0 ; i cm ; i++ ) {
for ( j = 0 ; j cn ; j++ ) {
printf(%4d\t, board[i][j] );
}
printf(\n);
}
printf (count = %d\n, count);
matrix_free(board);
system(PAUSE);
return 0;
}
BOOL check()
{
int i, j;
for ( i = 0 ; i M ; i++ ) {
for ( j = 0 ; j N ; j++ ) {
if ( board[i][j] == 0 )
return FALSE;
}
}
return TRUE;

} 고정상수 배열 코드

#include stdio.h
#inc
#include stdlib.h
#include time.h#define randomize() srand((unsigned)time(NULL))
typedef enum { FALSE, TRUE } BOOL;#define M 15
#define N 15int board[M][N] = { 0 };
int imove[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int jmove[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };BOOL check();int main()
{
int count = 0;
int ibug, jbug, i_temp, j_temp;
int i, j, k;printf(start i point(1 - %d) : , N );
scanf(%d, &ibug);
printf(start j point(1 - %d) : , M );
scanf(%d, &jbug);
board[--ibug][--jbug] = 1;randomize();while ( count = 50000 ) { if ( check() )
break; k = rand()%8;
i_temp = ibug + imove[k];
j_temp = jbug + jmove[k];
if ( ( i_temp = 0 && i_temp M ) &&
(j_temp = 0 && j_temp N ) ) {
ibug = i_temp;
jbug = j_temp;
count++;
board[ibug][jbug]++;
}

}for ( i = 0 ; i M ; i++ ) {
for ( j = 0 ; j N ; j++ ) {
printf(%4d, board[i][j] );
}
printf(\n);
}
printf (count = %d\n, count);return 0;
}BOOL check()
{
int i, j;for ( i = 0 ; i M ; i++ ) {
for ( j = 0 ; j N ; j++ ) {
if ( board[i][j] == 0 )
return FALSE;
}}return TRUE;
}

신청하기