0
웹에서 다운로드 한 "island of number"프로그램을 최적화하는 데 문제가 있습니다. 내가 아래에 설명 된대로 그것을 최적화했지만, couldnt 그것을 100 % 맞아.DFS 재귀 접근 방식을 사용하여 "Number of Islands"프로그램 최적화에서이 동작의 근본 원인이 될 수 있습니다
섬의 개수는 무엇입니까?
http://www.geeksforgeeks.org/find-number-of-islands/
I 주어진 그래프에서 섬의 수를 결정하는 웹 사이트 중 하나를 아래의 "C"프로그램을 가지고있다.
void DFS(int M[][COL], int row, int col, bool visited[][COL])
{
// These arrays are used to get row and column numbers of 8 neighbours
// of a given cell
static int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
static int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int k = 0;
// Mark this cell as visited
visited[row][col] = true;
printf("\n row=%d, col=%d", row, col);
// Recur for all connected neighbours
for (k = 0; k < 8; ++k) {
printf(" k=%d", k);
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k], col + colNbr[k], visited);
}
}
// The main function that returns count of islands in a given boolean
// 2D matrix
int countIslands(int M[][COL])
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
bool visited[ROW][COL];
memset(visited, 0, sizeof(visited));
// Initialize count as 0 and travese through the all cells of
// given matrix
int count = 0;
int i = 0, j=0;
for (i = 0; i < ROW; ++i) {
for (j = 0; j < COL; ++j) {
if (M[i][j] && !visited[i][j]) // If a cell with value 1 is not
{ // visited yet, then new island found
DFS(M, i, j, visited); // Visit all cells in this island.
++count; // and increment island count
printf("\n count is %d", count);
}
}
printf("\n");
}
return count;
}
// A function to check if a given cell (row, col) can be included in DFS
int isSafe(int M[][COL], int row, int col, bool visited[][COL])
{
// row number is in range, column number is in range and value is 1
// and not yet visited
printf(" (i=%d, j=%d)", row, col);
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL) &&
(M[row][col] && !visited[row][col]);
}
전체 행렬 크기에 대해 2 개의 for 루프를 사용하는 것이이 문제를 해결하는 가장 좋은 방법은 아니므로 다음과 같이 최적화를 시도했습니다.
내가 방문한 노드를 기억하는 것 외에도 is_visited 플래그에 대한 검사를 최적화하고 건너 뛰기 위해 인덱스 "i"와 "j"를 조작했습니다. 내 설명이 명확하길 바래. 아래 코드.
// A utility function to do DFS for a 2D boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS_new(int M[][COL], int *row, int *col, bool visited[][COL])
{
// These arrays are used to get row and column numbers of 8 neighbours
// of a given cell
int k;
static int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
static int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// Mark this cell as visited
visited[*row][*col] = true;
printf("\n row=%d, col=%d", *row, *col);
// Recur for all connected neighbours
for (k = 0; k < 8; ++k)
{
printf(" k=%d", k);
if (isSafe(M, (*row) + rowNbr[k], (*col) + colNbr[k], visited))
{
(*row) = (*row)+rowNbr[k];
(*col) = (*col)+colNbr[k];
DFS_new(M, row, col, visited);
}
}
}
// The main function that returns count of islands in a given boolean
// 2D matrix
int countIslands_new(int M[][COL])
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
bool visited[ROW][COL];
memset(visited, 0, sizeof(visited));
// Initialize count as 0 and travese through the all cells of
// given matrix
int count = 0;
int i = 0, j = 0;
while (i < ROW)
{
j = 0;
while (j < COL)
{
if (M[i][j] && !visited[i][j])
{
DFS_new(M, &i, &j, visited);
count++;
printf("\n count is %d", count);
}
j++;
}
i++;
}
return count;
}
이제 위의 두 프로그램을 테스트하기 위해 아래 입력을 사용하면 내 코드가 잘못된 결과를 제공합니다. 섬의 수가 4 인 것을 나타냅니다. 실제로는 3 개의 섬만 있습니다. 원래 프로그램은 잘 작동하지만.
// Driver program to test above function
int main()
{
int M[][COL]= { {1, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1}
};
printf("Number of islands is: %d\n", countIslands(M));
return 0;
}
내가 논리를 구축 할 수 없었던 한 가지 특별한 점은 아래와 같습니다.
내 프로그램에서 DFS_new 함수에서 내 프로그램의 코드 스 니펫 아래가이 함수가 다시 호출되는 것없이 8 회 이상 실행되는 것을 볼 수 있습니다. 즉 재귀 함수가 호출되지 않아도됩니다. 아래의 printf의
for (k = 0; k < 8; ++k)
{
printf(" k=%d", k);
}
출력 :이 질문은이 포럼에 대한 감각과 긍정적 인 반응을 기대한다
row=4, col=0 k=0 (i=3, j=-1) k=1 (i=3, j=0) k=2 (i=3, j=1) k=3 (i=4, j=-1)
k=4 (i=4, j=1) k=5 (i=5, j=-1) **k=6** (i=5, j=0) **k=7** (i=5, j=1)
**k=6** (i=4, j=1) **k=7** (i=4, j=2)
희망.
디버거 ........... –