题目：
地图分析
关键词
BFS
1162_1.c, 超时
//你现在手里有一份大小为 N x N 的「地图」（网格） grid，上面的每个「区域」（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，
//请你找出一个海洋区域，这个海洋区域到离它最近的陆地区域的距离是最大的。
//
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x
//1| + |y0 - y1| 。
//
// 如果我们的地图上只有陆地或者海洋，请返回 -1。
//
//
//
// 示例 1：
//
//
//
// 输入：[[1,0,1],[0,0,0],[1,0,1]]
//输出：2
//解释：
//海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
//
//
// 示例 2：
//
//
//
// 输入：[[1,0,0],[0,0,0],[0,0,0]]
//输出：4
//解释：
//海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。
//
//
//
//
// 提示：
//
//
// 1 <= grid.length == grid[0].length <= 100
// grid[i][j] 不是 0 就是 1
//
// Related Topics 广度优先搜索 图
//leetcode submit region begin(Prohibit modification and deletion)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint-gcc.h>
#include <stdbool.h>
#define MY_DEBUG(x, fmt...) printf(x, ##fmt)
//#define MY_DEBUG(x, fmt...)
#define MLOGD(x, fmt...) MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
//#define MLOGD(x, fmt...)
#define MLOGI(x, fmt...) MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
#define MLOGE(x, fmt...) MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))
typedef struct {
int x;
int y;
} PointType;
//uint8_t **g_visited = NULL;
uint8_t g_visited[100][100] = {0};
static void ClearMask(int rowMax, int colMax)
{
memset(g_visited, 0, sizeof(g_visited));
// int i;
// if (g_visited == NULL) {
// return;
// }
// for (i = 0; i < rowMax; i++) {
// memset(g_visited[i], false, colMax * sizeof(uint8_t));
// }
}
static int VisitedInit(int rowMax, int colMax)
{
// int i;
// uint8_t **visited = (uint8_t **)malloc(sizeof(int *) * rowMax);
// if (visited == NULL) {
// MLOGE("malloc error\n");
// return -1;
// }
// for (i = 0; i < rowMax; i++) {
// visited[i] = (uint8_t *)malloc(sizeof(uint8_t) * colMax);
// if (visited[i] == NULL) {
// MLOGE("malloc error\n");
// return -1;
// }
// memset(visited[i], false, sizeof(uint8_t) * colMax);
// }
// g_visited = visited;
memset(g_visited, 0, sizeof(g_visited));
return 0;
}
static void VisitedDeInit(int rowMax)
{
// int i;
// if (g_visited == NULL) {
// return;
// }
// for (i = 0; i < rowMax; i++) {
// free(g_visited[i]);
// g_visited[i] = NULL;
// }
// g_visited = NULL;
}
static int Bfs(int **grid, int rowMax, int colMax, int i, int j, const PointType *dest)
{
if (grid[i][j]) {
MLOGI("i=%d, j=%d, x=%d, y=%d\n", i, j, dest->x, dest->y);
return abs(i - dest->x) + abs(j - dest->y);
}
g_visited[i][j] = true;
int ret0 = rowMax + colMax;
int ret1 = rowMax + colMax;
int ret2 = rowMax + colMax;
int ret3 = rowMax + colMax;
if (((j - 1) >= 0) && (g_visited[i][j - 1] == false)) {
if (grid[i][j - 1] == 0) {
ret3 = Bfs(grid, rowMax, colMax, i, j - 1, dest);
} else {
ret3 = abs(i - dest->x) + abs(j - 1 - dest->y);
}
// MLOGI("x=%d, y=%d, ret3=%d\n", i, j - 1, ret3);
}
if (((j + 1) < rowMax) && (g_visited[i][j + 1] == false)){
if (grid[i][j + 1] == 0) {
ret2 = Bfs(grid, rowMax, colMax, i, j + 1, dest);
} else {
ret2 = abs(i - dest->x) + abs(j + 1 - dest->y);
}
// MLOGI("x=%d, y=%d, grid[i][j + 1]=%d, ret2=%d\n", i, j + 1, grid[i][j + 1], ret2);
}
if (((i - 1) >= 0) && (g_visited[i - 1][j]) == false) {
if (grid[i - 1][j] == 0) {
ret1 = Bfs(grid, rowMax, colMax, i - 1, j, dest);
} else {
ret1 = abs(i - 1 - dest->x) + abs(j - dest->y);
}
// MLOGI("x=%d, y=%d, ret1=%d\n", i - 1, j, ret1);
}
if (((i + 1) < rowMax) && (g_visited[i + 1][j] == false)) {
if (grid[i + 1][j] == 0) {
ret0 = Bfs(grid, rowMax, colMax, i + 1, j, dest);
} else {
ret0 = abs(i + 1 - dest->x) + abs(j - dest->y);
}
// MLOGI("x=%d, y=%d, ret0=%d\n", i + 1, j, ret0);
}
if ((ret0 + ret1 + ret2 + ret3) < (rowMax + colMax) * 4) {
ret0 = MIN(ret0, MIN(ret1, MIN(ret2, ret3)));
MLOGI("x=%d, y=%d, ret0=%d\n", dest->x, dest->y, ret0);
return ret0;
}
return rowMax + colMax;
}
int maxDistance(int** grid, int gridSize, int* gridColSize)
{
if ((grid == NULL) || (gridColSize == NULL)) {
MLOGE("null input\n");
return -1;
}
if (gridSize <= 0) {
MLOGE("grideSize is %d\n", gridSize);
return -1;
}
int i, j;
int distance = -1;
int ret = VisitedInit(gridSize, gridColSize[0]);
if (ret < 0) {
MLOGE("init visited buf error\n");
return -1;
}
PointType dest = {0};
for (i = 0; i < gridSize; i++) {
for (j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == 0) {
dest.x = i;
dest.y = j;
MLOGI("point(%d,%d) is 0, gridColSize[i]=%d\n", i, j, gridColSize[i]);
ret = Bfs(grid, gridSize, gridColSize[i], i, j, &dest);
if (ret != gridSize + gridColSize[i]) {
MLOGI("ret=%d, dest.x=%d, dest.y=%d\n", ret, dest.x, dest.y);
distance = MAX(distance, ret);
} else {
break;
}
ClearMask(gridSize, gridColSize[i]);
}
}
}
VisitedDeInit(gridSize);
return distance;
}
//leetcode submit region end(Prohibit modification and deletion)
1162_2.c
//你现在手里有一份大小为 N x N 的「地图」（网格） grid，上面的每个「区域」（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，
//请你找出一个海洋区域，这个海洋区域到离它最近的陆地区域的距离是最大的。
//
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x
//1| + |y0 - y1| 。
//
// 如果我们的地图上只有陆地或者海洋，请返回 -1。
//
//
//
// 示例 1：
//
//
//
// 输入：[[1,0,1],[0,0,0],[1,0,1]]
//输出：2
//解释：
//海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
//
//
// 示例 2：
//
//
//
// 输入：[[1,0,0],[0,0,0],[0,0,0]]
//输出：4
//解释：
//海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。
//
//
//
//
// 提示：
//
//
// 1 <= grid.length == grid[0].length <= 100
// grid[i][j] 不是 0 就是 1
//
// Related Topics 广度优先搜索 图
//leetcode submit region begin(Prohibit modification and deletion)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint-gcc.h>
#include <stdbool.h>
//#define MY_DEBUG(x, fmt...) printf(x, ##fmt)
#define MY_DEBUG(x, fmt...)
#define MLOGD(x, fmt...) MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
//#define MLOGD(x, fmt...)
#define MLOGI(x, fmt...) MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
#define MLOGE(x, fmt...) MY_DEBUG("[%s_%d]"x, __func__, __LINE__, ##fmt)
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))
typedef struct {
int x;
int y;
} PointType;
//uint8_t **g_visited = NULL;
uint8_t g_visited[100][100] = {0};
void ClearMask(int rowMax, int colMax)
{
memset(g_visited, 0, sizeof(g_visited));
// int i;
// if (g_visited == NULL) {
// return;
// }
// for (i = 0; i < rowMax; i++) {
// memset(g_visited[i], false, colMax * sizeof(uint8_t));
// }
}
int VisitedInit(int rowMax, int colMax)
{
// int i;
// uint8_t **visited = (uint8_t **)malloc(sizeof(int *) * rowMax);
// if (visited == NULL) {
// MLOGE("malloc error\n");
// return -1;
// }
// for (i = 0; i < rowMax; i++) {
// visited[i] = (uint8_t *)malloc(sizeof(uint8_t) * colMax);
// if (visited[i] == NULL) {
// MLOGE("malloc error\n");
// return -1;
// }
// memset(visited[i], false, sizeof(uint8_t) * colMax);
// }
// g_visited = visited;
memset(g_visited, 0, sizeof(g_visited));
return 0;
}
static void VisitedDeInit(int rowMax)
{
// int i;
// if (g_visited == NULL) {
// return;
// }
// for (i = 0; i < rowMax; i++) {
// free(g_visited[i]);
// g_visited[i] = NULL;
// }
// g_visited = NULL;
}
static int g_currOceanCnt = 0;
static int Bfs(int **grid, int rowMax, int colMax, int i, int j, int level)
{
if (grid[i][j] == 0) {
grid[i][j] = 1 + level;
g_currOceanCnt --;
MLOGI("i=%d, j=%d, *level=%d\n", i, j, level);
return true;
}
int ret0 = false;
int ret1 = false;
int ret2 = false;
int ret3 = false;
if (((j - 1) >= 0) && (grid[i][j - 1] == false)) {
ret3 = Bfs(grid, rowMax, colMax, i, j - 1, level);
}
if (((j + 1) < rowMax) && (grid[i][j + 1] == false)) {
ret2 = Bfs(grid, rowMax, colMax, i, j + 1, level);
}
if (((i - 1) >= 0) && (grid[i - 1][j]) == false) {
ret1 = Bfs(grid, rowMax, colMax, i - 1, j, level);
}
if (((i + 1) < rowMax) && (grid[i + 1][j] == false)) {
ret0 = Bfs(grid, rowMax, colMax, i + 1, j, level);
}
if ((ret0 + ret1 + ret2 + ret3) != false) {
return true;
}
return false;
}
int maxDistance(int** grid, int gridSize, int* gridColSize)
{
if ((grid == NULL) || (gridColSize == NULL)) {
MLOGE("null input\n");
return -1;
}
if (gridSize <= 0) {
MLOGE("grideSize is %d\n", gridSize);
return -1;
}
int i, j;
int ret = VisitedInit(gridSize, gridColSize[0]);
if (ret < 0) {
MLOGE("init visited buf error\n");
return -1;
}
int level = 0;
int oceanCnt = 0;
for (i = 0; i < gridSize; i++) {
for (j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == 0) {
oceanCnt++;
}
}
}
if ((oceanCnt == 0) || (oceanCnt == (gridSize * gridColSize[0]))) {
return -1;
}
g_currOceanCnt = oceanCnt;
while (g_currOceanCnt != 0) {
level++;
for (i = 0; i < gridSize; i++) {
for (j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == level) {
MLOGI("point(%d,%d) = %d, gridColSize[i]=%d\n", i, j, grid[i][j], gridColSize[i]);
ret = Bfs(grid, gridSize, gridColSize[i], i, j, grid[i][j]);
}
}
}
}
VisitedDeInit(gridSize);
if (level == 0) {
level = -1;
}
return level;
}
网友评论