Cアルゴリズム-DFS(深さ優先探索法)

leetcode 200題、島の数.2 Dマトリクス、1は陸地を表し、つながって島を計算し、島の数を返します.leetcode 130題、囲まれたエリア.2ビットマトリクスは、0が1で囲まれている場合、0を1 leetcode 417題に記入し、太平洋大西洋の水流問題が上から下へ流れる水は、左から右へ流れる水markから出て、他の2方向の格納配列2の中にある.保存方法はdfsです
dfsループは,以前に紹介した遡及スタイルとは少し異なるCアルゴリズム−貪欲/遡及/剪定1,forループノードと,いつ再帰するかを判断し,主関数に置くと,遡及スタイルとは明らかに異なる.2、dfs構造:a、ifアウトxxx;b、ifはxxxに訪問されたことがある.c、タグアクセス;d、dfs(next)3、条件を満たす場所は必ず記入してください
200島問題

void dfs(char **grid,int row, int col, int i ,int j) {
    if (i < 0 || j < 0 || i >=row || j >=col) {
        return;
    }
    if (grid[i][j] == '0') {
        return;
    }
    grid[i][j] = '0';
    dfs(grid, row, col, i+1, j);
    dfs(grid, row, col, i-1, j);
    dfs(grid, row, col, i, j+1);
    dfs(grid, row, col, i, j-1);
}

int numIslands(char** grid, int gridSize, int* gridColSize){
    int i, j, col, row, count;
    if (gridSize == 0) {
        return 0;
    }
    col = *gridColSize;
    row = gridSize;
    count = 0;
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, row, col, i, j);
            }
        }
    }
    return count;
}

130を囲む領域

void dfs(int i, int j, char **board, int row, int col)
{
	if (i < 0 || j < 0 || i >= row || j >= col) {
		return;
	}
	if (board[i][j] != 'O') {
		return;
	}
    board[i][j] = 'B';
	dfs(i + 1, j, board, row, col);
	dfs(i - 1, j, board, row, col);
	dfs(i, j + 1, board, row, col);
	dfs(i, j - 1, board, row, col);
	return;
}

void solve(char** board, int boardSize, int* boardColSize) {
	int i, j;
	int col, row;
	if (boardSize == 0) {
		return;
	}
	row = boardSize;
	col = *boardColSize;
	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
			if (i != 0 && i != row - 1 && j!= 0 && j!= col -1 ) {
                continue;
            }
            if (board[i][j] == 'X') {
				continue;
			}
			dfs(i, j, board, row, col);
		}
	}
	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
            if (board[i][j] == 'O') {
				board[i][j] = 'X';
			}
		}
	}
	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
            if (board[i][j] == 'B') {
				board[i][j] = 'O';
			}
		}
	}
	return;
}

417太平洋大西洋の水流問題

#define MAXLEN 160 
int ocean1[MAXLEN][MAXLEN];
int ocean2[MAXLEN][MAXLEN];
void dfs(int ** matrix, int row, int col, int i, int j, int count, int flag)
{
	if (i < 0 || j < 0 || i >= row || j >= col) {
		return;
	}
	if (matrix[i][j] < count) {
		return;
	}
	if (flag == 0 && ocean1[i][j] == 1) {
		return;
	}
	if (flag == 1 && ocean2[i][j] == 1) {
		return;
	}
	if (flag == 0) {
		ocean1[i][j] = 1;
	}
	if (flag == 1) {
		ocean2[i][j] = 1;
	}
	dfs(matrix, row, col, i + 1, j, matrix[i][j], flag);
	dfs(matrix, row, col, i - 1, j, matrix[i][j], flag);
	dfs(matrix, row, col, i, j + 1, matrix[i][j], flag);
	dfs(matrix, row, col, i, j - 1, matrix[i][j], flag);
}

int** pacificAtlantic(int** matrix, int matrixSize, int* matrixColSize, int* returnSize, int** returnColumnSizes) {
	if (matrixSize == 0) {
		*returnSize = 0;
		return NULL;
	}

	int row, col, i, j, count;
	int tmp[MAXLEN*MAXLEN][2];
	row = matrixSize;
	col = *matrixColSize;
	count = 0;
	memset(ocean1, 0, sizeof(int)*MAXLEN*MAXLEN);
	memset(ocean2, 0, sizeof(int)*MAXLEN*MAXLEN);
	i = 0;
	for (j = 0; j < col; j++) {
		dfs(matrix, row, col, i, j, 0, 0);
	}
	j = 0;
	for (i = 0; i < row; i++) {
		dfs(matrix, row, col, i, j, 0, 0);
	}
	i = row - 1;
	for (j = 0; j < col; j++) {
		dfs(matrix, row, col, i, j, 0, 1);
	}
	j = col - 1;
	for (i = 0; i < row; i++) {
		dfs(matrix, row, col, i, j, 0, 1);
	}
	count = 0;
	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
			if (ocean1[i][j] && ocean2[i][j]) {
				tmp[count][0] = i;
				tmp[count][1] = j;
				count++;
			}
		}
	}
	*returnSize = count;
	int **ret = (int**)malloc(sizeof(int*)*count);
	*returnColumnSizes = (int*)malloc(sizeof(int)*count);
	int *total = (int*)malloc(sizeof(int)*count * 2);
	for (i = 0; i < count; i++) {
		ret[i] = total + 2 * i;
		ret[i][0] = tmp[i][0];
		ret[i][1] = tmp[i][1];
		(*returnColumnSizes)[i] = 2;
	}

	return ret;

}