
题目地址 : https://kamacoder.com/problempage.php?pid=1175
我这边思路 搞一个cache数组记录每个路径递归过程中的结果 如果flag&1为真 说明能到达左上边界 如果flag&2 为真则能到达 右下边界
#include <ctype.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 存在两个路径 一条能碰到左边界,一条能碰都右边界*/
int N, M;
int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int dfs(int graph[N][M], int used[N][M], int cache[N][M], int x, int y)
{
int flag = 0;
if (y == 0 || x == 0)
flag |= 1;
if (y == M - 1 || x == N - 1)
flag |= 2;
used[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int nextx = x + direction[i][0];
int nexty = y + direction[i][1];
//先查找是否有缓存数据?
if (nextx >= 0 && nextx < N && nexty >= 0 && nexty < M)
{
if (cache[nextx][nexty])
flag |= cache[nextx][nexty];
else if (!used[nextx][nexty] && graph[nextx][nexty] <= graph[x][y])
{
flag |= dfs(graph, used, cache, nextx, nexty);
}
}
}
cache[x][y] = flag;
// if (cache[x][y] & 1 && cache[x][y] & 2)
// printf("坐标:%d %d\n", x, y);
return flag;
}
int main()
{
scanf("%d %d", &N, &M);
int graph[N][M];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
scanf("%d", &graph[i][j]);
}
int used[N][M];
memset(used, 0, sizeof(used));
//在搞一个数组记录每个节点是否能碰到边界?
int cache[N][M]; // 1 表示能碰到左上边界 2表示能碰到右下边界
memset(cache, 0, sizeof(cache));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (!used[i][j])
dfs(graph, used, cache, i, j);
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if ((cache[i][j] & 1) && (cache[i][j] & 2))
{
printf("%d %d\n", i, j);
}
}
}
return 0;
}测试了一个用例:
5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1
正确结果
0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1
这个用例我代码也没问题 但是有的过不去 请大佬指点下