【算法/搜索】贪吃蛇

#include <stdio.h>
#include <string.h>
#include <math.h>
#include "io.h"
#define MAXN 20

char map[MAXN][MAXN], vis[MAXN][MAXN][MAXN * MAXN][4];
int k;
int ex, ey;
int n, m;
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

int in(int x, int y)
{
    return (x >= 0 && x < n && y >= 0 && y < m);
}
char visnake[10];
int ans = MAXN * MAXN * 10;
int sx, sy;
// walk
int tmp = 0;
void walk(char tmpmap[MAXN][MAXN], int x, int y, int tox, int toy)
{
    if (tmpmap[tox][toy] == '0' + k)
    {
        tmp = tmpmap[tox][toy] - '0';
    }
    tmpmap[tox][toy] = tmpmap[x][y];
    if (tmpmap[x][y] == '0' + k)
    {
        tmpmap[x][y] = '.';
    }
    if ((tmp) && (tmpmap[tox][toy] == tmp - 1 + '0'))
    {
        tmpmap[x][y] = tmp + '0';
    }
    int nx = x, ny = y;
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tmpmap[tx][ty] == tmpmap[x][y] + 1)
        {
            visnake[tmpmap[tx][ty] - '0'] = 1;
            nx = tx, ny = ty;
            break;
        }
    }
    if (nx == x && ny == y)
    {
        return;
    }
    walk(tmpmap, nx, ny, x, y);
}
// update
void update(char tmpmap[MAXN][MAXN], int sx, int sy, int tx, int ty)
{
    tmp = 0;
    memset(visnake, 0, sizeof(visnake));
    walk(tmpmap, sx, sy, tx, ty);
    //disp(tmpmap, n, m); // 每update一次就输出
}

struct node
{
    char map[MAXN][MAXN];
    int x, y;
    int step;
    int dir;
} q[MAXN * MAXN * 10];

struct node make_node(const char map[MAXN][MAXN], int x, int y, int step, int dir)
{
    struct node tmp;
    memcpy(tmp.map, map, MAXN * MAXN);
    tmp.x = x, tmp.y = y;
    tmp.step = step;
    tmp.dir = dir;
    return tmp;
}

int bfs()
{
    int l = 0, r = 0;
    for (int i = 0; i < 4; i++)
    {
        char tmp[MAXN][MAXN];
        memcpy(tmp, map, MAXN * MAXN);
        int tx = sx + dir[i][0];
        int ty = sy + dir[i][1];
        if (in(tx, ty) && !vis[tx][ty][1][i] && ((tmp[tx][ty] == '0' + k&&k!=2) || tmp[tx][ty] == '@' || tmp[tx][ty] == '.'))
        {
            vis[tx][ty][1][i] = 1;
            update(tmp, sx, sy, tx, ty);
            q[r++] = make_node(tmp, tx, ty, 1, i);
        }
    }
    while (l < r)
    {
        struct node tmp = q[l++];
        char tmpmap[MAXN][MAXN];
        memcpy(tmpmap, tmp.map, MAXN * MAXN);
        for (int i = 0; i < 4; i++)
        {
            memcpy(tmpmap, tmp.map, MAXN * MAXN);
            int tx = tmp.x + dir[i][0], ty = tmp.y + dir[i][1];
            if (in(tx, ty) && !vis[tx][ty][tmp.step + 1][i] && (((tmpmap[tx][ty] == '0' + k&&k!=2)) || (tmpmap[tx][ty] == '@') || (tmpmap[tx][ty] == '.')))
            {
                if(tmpmap[tx][ty]=='@')
                {
                    return tmp.step+1;
                }
                vis[tx][ty][tmp.step + 1][i] = 1;
                update(tmpmap, tmp.x, tmp.y, tx, ty);
                q[r++] = make_node(tmpmap, tx, ty, tmp.step + 1, i);
            }
        }
    }
    return -1;
}

void user_control()
{
    //disp(map, n, m);
    int ch;

    while (scanf("%d", &ch))
    {
        switch (ch)
        {
        case 2:
            // down
            update(map, sx, sy, sx + 1, sy);
            sx++;
            break;
        case 4:
            // left
            update(map, sx, sy, sx, sy - 1);
            sy--;
            break;
        case 8:
            // up
            update(map, sx, sy, sx - 1, sy);
            sx--;
            break;
        case 6:
            // right
            update(map, sx, sy, sx, sy + 1);
            sy++;
            break;
        default:
            break;
        }
    }
}
#define RUN
int main()
{
    // freopen("out.txt", "w+", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", map[i]);
    }

    disp(map, n, m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] >= '1' && map[i][j] <= '9')
            {
                if (map[i][j] - '0' > k)
                {
                    k = map[i][j] - '0';
                }
            }
            if (map[i][j] == '1')
            {
                sx = i, sy = j;
            }
            if (map[i][j] == '@')
            {
                ex = i, ey = j;
            }
        }
    }
#ifdef RUN
    printf("%d", bfs());
#endif
#ifdef DEBUG
    user_control();
#endif
}