104 lines
2.8 KiB
C++
104 lines
2.8 KiB
C++
#include <cstdlib>
|
|
#include <cstring>
|
|
#include <iostream>
|
|
#include <string>
|
|
|
|
using namespace std;
|
|
|
|
class Grid {
|
|
public:
|
|
Grid(const double p, const int x, const int y) : m(x), n(y) {
|
|
const int thresh = static_cast<int>(RAND_MAX * p);
|
|
|
|
// Allocate two addition rows to avoid checking bounds.
|
|
// Bottom row is also required by drippage
|
|
start = new cell[m * (n + 2)];
|
|
cells = start + m;
|
|
for (auto i = 0; i < m; i++) start[i] = RBWALL;
|
|
end = cells;
|
|
for (auto i = 0; i < y; i++) {
|
|
for (auto j = x; --j;)
|
|
*end++ = (rand() < thresh ? BWALL : 0) | (rand() < thresh ? RWALL : 0);
|
|
*end++ = RWALL | (rand() < thresh ? BWALL : 0);
|
|
}
|
|
memset(end, 0u, sizeof(cell) * m);
|
|
}
|
|
|
|
~Grid() {
|
|
delete[] start;
|
|
cells = 0;
|
|
start = 0;
|
|
end = 0;
|
|
}
|
|
|
|
int percolate() const {
|
|
auto i = 0;
|
|
for (; i < m && !fill(cells + i); i++);
|
|
return i < m;
|
|
}
|
|
|
|
void show() const {
|
|
for (auto j = 0; j < m; j++)
|
|
cout << ("+-");
|
|
cout << '+' << endl;
|
|
|
|
for (auto i = 0; i <= n; i++) {
|
|
cout << (i == n ? ' ' : '|');
|
|
for (auto j = 0; j < m; j++) {
|
|
cout << ((cells[i * m + j] & FILL) ? "#" : " ");
|
|
cout << ((cells[i * m + j] & RWALL) ? '|' : ' ');
|
|
}
|
|
cout << endl;
|
|
|
|
if (i == n) return;
|
|
|
|
for (auto j = 0; j < m; j++)
|
|
cout << ((cells[i * m + j] & BWALL) ? "+-" : "+ ");
|
|
cout << '+' << endl;
|
|
}
|
|
}
|
|
|
|
private:
|
|
enum cell_state {
|
|
FILL = 1 << 0,
|
|
RWALL = 1 << 1, // right wall
|
|
BWALL = 1 << 2, // bottom wall
|
|
RBWALL = RWALL | BWALL // right/bottom wall
|
|
};
|
|
|
|
typedef unsigned int cell;
|
|
|
|
bool fill(cell* p) const {
|
|
if ((*p & FILL)) return false;
|
|
*p |= FILL;
|
|
if (p >= end) return true; // success: reached bottom row
|
|
|
|
return (!(p[0] & BWALL) && fill(p + m)) || (!(p[0] & RWALL) && fill(p + 1))
|
|
||(!(p[-1] & RWALL) && fill(p - 1)) || (!(p[-m] & BWALL) && fill(p - m));
|
|
}
|
|
|
|
cell* cells;
|
|
cell* start;
|
|
cell* end;
|
|
const int m;
|
|
const int n;
|
|
};
|
|
|
|
int main() {
|
|
const auto M = 10, N = 10;
|
|
const Grid grid(.5, M, N);
|
|
grid.percolate();
|
|
grid.show();
|
|
|
|
const auto C = 10000;
|
|
cout << endl << "running " << M << "x" << N << " grids " << C << " times for each p:" << endl;
|
|
for (auto p = 1; p < M; p++) {
|
|
auto cnt = 0, i = 0;
|
|
for (; i < C; i++)
|
|
cnt += Grid(p / static_cast<double>(M), M, N).percolate();
|
|
cout << "p = " << p / static_cast<double>(M) << ": " << static_cast<double>(cnt) / i << endl;
|
|
}
|
|
|
|
return EXIT_SUCCESS;
|
|
}
|