私はBFSの演習を解決しようとしていますが、ideoneのコンパイラを使用すると、このコンパイラが機能し、この入力の正しい出力である「24」が出力されます。
7 8
..#...##
.##.....
###.A..A
.#......
.#....A.
...A....
........
完全なコードは次のとおりです。
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define MAX 1001
struct node
{
int x;
int y;
int distance;
};
int l, c;
char grid[MAX][MAX], temp;
node clouds[MAX * MAX];
int n_clouds = 0;
int i, u;
int visited[MAX][MAX];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
int n_min, n_max;
inline int max(int a, int b)
{
return a > b ? a : b;
}
inline int min(int a, int b)
{
return a < b ? a : b;
}
void read_input()
{
scanf("%d %d", &l, &c);
for (i = 0; i < l; i++)
{
for (u = 0; u < c; u++)
{
scanf(" %c", &temp);
grid[i][u] = temp;
if (temp == '#')
{
node cloud;
cloud.x = u;
cloud.y = i;
clouds[n_clouds] = cloud;
n_clouds++;
}
}
}
}
void bfs(node start)
{
queue<node> q;
q.push(start);
memset(visited, 0, sizeof visited);
while (!q.empty())
{
node current = q.front();
q.pop();
int x = current.x;
int y = current.y;
int distance = current.distance;
if (x < 0 || y < 0 || x >= c || y >= l || visited[y][x])
{
continue;
}
//printf("x: %d, y: %d\n", x, y);
visited[y][x] = 1;
if (grid[y][x] == 'A')
{
printf("distance: %d\n", distance);
if (n_min == -1)
n_min = distance;
else
n_min = min(n_min, distance);
n_max = max(n_max, distance);
return;
}
node node;
node.distance = distance + 1;
int k;
for (k = 0; k < 4; k++)
{
node.x = x + dx[k];
node.y = y + dy[k];
q.push(node);
//printf("node.x = %d, node.y = %d, k = %d\n", node.x, node.y, k);
}
}
}
int main()
{
read_input();
n_min = -1;
n_max = -1;
for (i = 0; i < n_clouds; i++)
{
bfs(clouds[i]);
}
printf("%d %d\n", n_min, n_max);
return 0;
}
コンパイルに使用g++ file.cpp -o fileしています。これは、4GBのRAMラップトップのローカル出力です。
distance: 4196516
distance: 4196515
distance: 4196514
distance: 4196516
distance: 4196515
distance: 4196516
distance: 4196515
distance: 4196514
distance: 4196516
distance: 4196515
4196514 4196516
これは、ideoneの出力とは大きく異なります。
distance: 4
distance: 3
distance: 2
distance: 4
distance: 3
distance: 4
distance: 3
distance: 2
distance: 4
distance: 3
2 4
これはおそらく[MAX][MAX]2次元配列が原因のある種のメモリエラーだと思いますが、[1001][1001]配列を使用できると思いました。何が起こっているのかについてのアイデアが必要です。また、これはどの入力でも発生すると思います。これを使用すると、奇妙な膨大な数も得られるからです。
3 3
#..
...
..A
ideoneで、正しい出力が得られます。
distance: 4
4 4
このプログラムは、任意の雲（'＃'）から空港（'A'）までの最小距離と最大距離を計算することになっています。
これがvalgrindの出力です。メモリエラーを報告しているとは思いません。
~/src/oni> valgrind ./nuvemcinzas < nuvemcinzas_input.txt
==20861== Memcheck, a memory error detector
==20861== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==20861== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==20861== Command: ./nuvemcinzas
==20861==
==20861== Conditional jump or move depends on uninitialised value(s)
==20861== at 0x53954F1: vfprintf (vfprintf.c:1629)
==20861== by 0x539E8D8: printf (printf.c:35)
==20861== by 0x400C71: bfs(node) (in /home/david/src/oni/nuvemcinzas)
==20861== by 0x400E25: main (in /home/david/src/oni/nuvemcinzas)
==20861==
==20861== Use of uninitialised value of size 8
==20861== at 0x53937EB: _itoa_word (_itoa.c:195)
==20861== by 0x5395837: vfprintf (vfprintf.c:1629)
==20861== by 0x539E8D8: printf (printf.c:35)
==20861== by 0x400C71: bfs(node) (in /home/david/src/oni/nuvemcinzas)
==20861== by 0x400E25: main (in /home/david/src/oni/nuvemcinzas)
==20861==
==20861== Conditional jump or move depends on uninitialised value(s)
==20861== at 0x53937F5: _itoa_word (_itoa.c:195)
==20861== by 0x5395837: vfprintf (vfprintf.c:1629)
==20861== by 0x539E8D8: printf (printf.c:35)
==20861== by 0x400C71: bfs(node) (in /home/david/src/oni/nuvemcinzas)
==20861== by 0x400E25: main (in /home/david/src/oni/nuvemcinzas)
==20861==
distance: 4196516
==20861== Conditional jump or move depends on uninitialised value(s)
==20861== at 0x400EB9: max(int, int) (in /home/david/src/oni/nuvemcinzas)
==20861== by 0x400CBA: bfs(node) (in /home/david/src/oni/nuvemcinzas)
==20861== by 0x400E25: main (in /home/david/src/oni/nuvemcinzas)
==20861==
distance: 4196515
==20861== Conditional jump or move depends on uninitialised value(s)
==20861== at 0x400C7B: bfs(node) (in /home/david/src/oni/nuvemcinzas)
==20861== by 0x400E25: main (in /home/david/src/oni/nuvemcinzas)
==20861==
==20861== Conditional jump or move depends on uninitialised value(s)
==20861== at 0x400ED5: min(int, int) (in /home/david/src/oni/nuvemcinzas)
==20861== by 0x400C9F: bfs(node) (in /home/david/src/oni/nuvemcinzas)
==20861== by 0x400E25: main (in /home/david/src/oni/nuvemcinzas)
==20861==
distance: 4196514
distance: 4196516
distance: 4196515
distance: 4196516
distance: 4196515
distance: 4196514
distance: 4196516
distance: 4196515
==20861== Conditional jump or move depends on uninitialised value(s)
==20861== at 0x53954F1: vfprintf (vfprintf.c:1629)
==20861== by 0x539E8D8: printf (printf.c:35)
==20861== by 0x400E66: main (in /home/david/src/oni/nuvemcinzas)
==20861==
==20861== Use of uninitialised value of size 8
==20861== at 0x53937EB: _itoa_word (_itoa.c:195)
==20861== by 0x5395837: vfprintf (vfprintf.c:1629)
==20861== by 0x539E8D8: printf (printf.c:35)
==20861== by 0x400E66: main (in /home/david/src/oni/nuvemcinzas)
==20861==
==20861== Conditional jump or move depends on uninitialised value(s)
==20861== at 0x53937F5: _itoa_word (_itoa.c:195)
==20861== by 0x5395837: vfprintf (vfprintf.c:1629)
==20861== by 0x539E8D8: printf (printf.c:35)
==20861== by 0x400E66: main (in /home/david/src/oni/nuvemcinzas)
==20861==
4196514 4196516
==20861==
==20861== HEAP SUMMARY:
==20861== in use at exit: 0 bytes in 0 blocks
==20861== total heap usage: 49 allocs, 49 frees, 15,896 bytes allocated
==20861==
==20861== All heap blocks were freed -- no leaks are possible
==20861==
==20861== For counts of detected and suppressed errors, rerun with: -v
==20861== Use --track-origins=yes to see where uninitialised values come from
==20861== ERROR SUMMARY: 208 errors from 9 contexts (suppressed: 2 from 2)