#include <iostream>
#include <cstdlib>
#include "grid.h"

using namespace std;

int main() {

    int N; // lattice size
    int T; // number of trials
    int deadEnds = 0;

    cin >> N >> T;

    // simulate T self-avoiding walks
    for (int t = 0; t < T; ++t) {
        Grid<bool> a(N, N);    // intersections visited
        int x = N/2;           // current position
        int y = N/2;

        // repeatedly take a random step, unless you've already escaped
        while (x > 0 && x < N-1 && y > 0 && y < N-1) {
            // dead-end, so break out of loop
            if (a[x-1][y] && a[x+1][y] && a[x][y-1] && a[x][y+1]) {
                ++deadEnds;
                break;
            }

            a[x][y] = true;     // mark as visited

            // take a random step to unvisited neighbour
            double r = (static_cast<double>(rand()) / static_cast<double>(RAND_MAX));
            if (r < 0.25) {
                if (!a[x+1][y])
                    ++x;
            } else if (r < 0.50) {
                if (!a[x-1][y])
                    --x;
            } else if (r < 0.75) {
                if (!a[x][y+1])
                    ++y;
            } else {
                if (!a[x][y-1])
                    --y;
            }
        }
    }
    cout << 100*deadEnds/T << "% dead ends" << endl;
    return 0;
}