알고리즘 문제를 풀고 있는데, 어느 부분에서 시간이 오래걸리는지 찾아주실 분...

CTU Open Contest 2014년도 대회문제 중
Karel the Robot 이란 알고리즘 문제를 풀고 있습니다

일단 제가 도움을 요청드리는 부분은 제 알고리즘 소스와 모범답안의 소스는
변수이름 정도만 다르고 순서도는 거의 같다는 것이 저의 생각입니다.
(아닐 수도 있지만 제 소스와 답안 소스를 비교해보시면 수긍하시리라 생각합니다)

그런데 실행시간에 있어서는 너무 큰 시간 차이를 보여주는데,
이게 어느 부분에서 시간 차이가 생기는지 알아내려 노력해봤지만
알 수가 없어 도움을 요청하고자 합니다...

* 알고리즘 문제를 간단히 한글로 설명드리자면 Karel 이란 로봇이 있는데

1. 3 종류의 명령어를 실행할 수 있습니다 전진(S), 시계 방향 회전(R), 반시계 방향 회전(L)

2. 문제에는 이 로봇이 수행할 명령어 집합이 입력되고 최대 저장공간은 10칸(즉, 1 ~ 10개의 명령어 저장가능)으로

3. 마지막 명령어가 실행된 후에는 첫 번째 명령어로 돌아가 계속 실행하게 됩니다.

4. 문제에는 이 로봇이 명령을 수행하게 될 미로가 입력되고(높이, 너비, 지형) 지형은 탈출구, 빈공간, 벽이 입력됩니다.
(탈출구와 빈공간은 합쳐서 자유 공간으로 불리게 됩니다)

5. 로봇은 문제에서 제시된 지형의 모든 자유 공간에서 시작되며, 시작시 무조건 을 바라보고 시작합니다.

6. 문제의 답안은 로봇이 문제에서 제시한 명령어를 실행하여 탈출 가능한 자유 공간 시작 위치의 개수를 출력하면 됩니다.
= 명령어 집합을 영원히 실행하여도 탈출이 불가능한 경우의 수를 알아내어 전체 경우의 수에서 빼준 개수를 출력

7. 문제의 자유공간(탈출구 포함) 개수와 문제의 답안이 일치한다면 OK를 출력하면 됩니다.

※ 대회 모범답안은 입력이 이상하게 되길래 첨부해 놓았습니다.(모범 답안은 콘솔 입출력)

제 알고리즘 소스는 아래와 같고(입출력은 첨부된 파일을 통해)

#include "stdio.h"
#include "Windows.h"
#include "time.h"

char strCmd[11] = {0, };
char arsMaze[100][101] = {0, };

int unRoadAlreadyBeen[100][100][10][4] = {0, };
int nTry = 0;

int nFreeTerrain;

int x, y;

int nHeight;
int nWidth;
int nCmdLen;

int dir;

int nResult;

void Init();
void InitRobot(int x, int y);

bool check(int x, int y);

void DoAllCase();
void DoCmd();

int main()
{
FILE *in, *out;

in = fopen("input.txt", "r+");
out = fopen("output.txt", "w");

int i;
bool bContinue;

do
{
nResult = 0;
nFreeTerrain = 0;

if( fscanf(in, "%d %d", &nHeight, &nWidth) != 2 )
break;

for( i = 0 ; i fscanf(in, "%s", arsMaze[i]);

fscanf(in, "%d", &nCmdLen);

bContinue = (bool)(fscanf(in, "%s", strCmd) != EOF);

DoAllCase();

if( nResult == nFreeTerrain )
fprintf(out, "OK\n");
else
fprintf(out, "%d\n", nResult);
}
while( bContinue );

fclose(in);
fclose(out);

return 0;
}

void DoAllCase()
{
clock_t start, end;
int i, j, cnt;

start = clock();

for( i = 0 ; i {
for( j = 0 ; j {
if( arsMaze[i][j] == 'X' )
continue;

nFreeTerrain++;
nTry++;

cnt = 0;
dir = 0;

x = j; y = i;

while( true )
{
if( arsMaze[y][x] == 'E' )
{
nResult++;
break;
}

if( unRoadAlreadyBeen[y][x][cnt][dir] == nTry )
break;
else
unRoadAlreadyBeen[y][x][cnt][dir] = nTry;

switch( strCmd[cnt] )
{
case 'S':
switch( dir )
{
case 0:
if( check(x, y - 1) )
y -= 1;
break;
case 1:
if( check(x + 1, y) )
x += 1;
break;
case 2:
if( check(x, y + 1) )
y += 1;
break;
case 3:
if( check(x - 1, y) )
x -= 1;
break;
}
break;
case 'L':
dir = (dir + 3) % 4;
break;
case 'R':
dir = (dir + 1) % 4;
break;
}

cnt = (cnt + 1) % nCmdLen;
}
}
}

end = clock();

printf("[%d] : %f\n", nTry, ((double)(end - start)) / CLOCKS_PER_SEC);
}

bool check(int x, int y)
{
return (x = nWidth || y = nHeight || arsMaze[y][x] == 'X') ? false : true;
}