migong.cpp

【问题描述】 在一个N*N的点阵中

#include <fstream>
using namespace std;

ifstream in("migong.in");
ofstream out("migong.out");

int f = 1, r = 0, prev[10001], map[1001][1001], flag = 0;
const int drt[8][2] = {{-1, -1}, {-1, 0},
                       {-1, 1}, {0, 1},
                       {1, 1}, {1, 0},
                       {1, -1}, {0, -1}};

struct coordinate
{
    int x, y;
    coordinate()
    {
        x = y = 0;
    }
    coordinate(int a, int b)
    {
        x = a;
        y = b;
    }
    void addx(coordinate* q)
    {
        if(!search(q))
        {
            q[++r] = *this;
            prev[r] = f - 1;
        }
    }
    bool search(coordinate* q)
    {
        for(int i = 1; i <= r; i++)
            if(q[i] == *this)
                return true;
        return false;
    }
    bool operator == (coordinate c)
    {
        if((c.x == this->x)
         &&(c.y == this->y))
            return true;
        return false;
    }
}que[10001], exi;

ostream& operator << (ostream& out, coordinate c)
{
    out << "(" << c.x << "," << c.y <<")";
    return out;
}

int main()
{
    void print(int x);
    void printcnt(int x, int cnt);
    void coordgen(coordinate c);
    void read();

    memset(prev, 0, sizeof prev);
    memset(map, 0, sizeof map);

    read();
    coordinate ent(1, 1);
    ent.addx(que);

    while(!(que[r] == exi))
        if(f != r + 1)
            coordgen(que[f++]);
        else
        {
            flag = 1;
            break;
        }

    if(flag)
    {
        out << "impossible" << endl;
        return 0;
    }
    
    printcnt(r, 1);
    out<<ent; print(r); out<<endl;

    return 0;
}

void read()
{
    int kx, ky;
    in >> exi.x >> exi.y;
    in >> kx >> ky;
    for(int i = 0; i <= kx + 1; i++)
    {
        map[i][0] = 1;
        map[i][ky + 1] = 1;
    }
    for(int i = 0; i <= ky + 1; i++)
    {
        map[0][i] = 1;
        map[kx + 1][i] = 1;
    }
    for(int i = 1; i <= kx; i++)
        for(int j = 1; j <= ky; j++)
            in>>map[i][j];
}

void coordgen(coordinate c)
{
    for(int i = 0; i <= 7; i++)
    {
        coordinate t = c;
        t.x += drt[i][0];
        t.y += drt[i][1];
        if(map[t.x][t.y] == 0)
            t.addx(que);
    }
}

void print(int x)
{
    if(prev[x] != 1)
        print(prev[x]);
    out << "->" << que[x];
}

void printcnt(int x, int cnt)
{
    if(prev[x] != 1)
        printcnt(prev[x], ++cnt);
    if(prev[x] == 1)
        out << cnt << endl;
}