【贪吃蛇问题】_可能有不少的同学玩过“贪吃蛇“的游戏,游戏中蛇头带动整个蛇的移动,蛇身将沿蛇头

问题：

思路：

回溯法

代码（6.7更新，把sign去掉了）：

#include<bits/stdc++.h>
using namespace std;
#define exit_x 1
#define exit_y 1
 
int n, m, l, k;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int best = INT_MAX;
 
int solve(int **blocks, int h, int t, int *snake_x, int *snake_y, int total)
{
    int result  = INT_MAX;
    
    if(total >= best) return total;
 
    int head_x = snake_x[h], head_y = snake_y[h]; 
 
    if(head_x == exit_x && head_y == exit_y)
    {
        best = total;
        return total;
    }
 
    for(int i = 0; i < 4; i++)
    {
        int new_x = head_x + dx[i];
        int new_y = head_y + dy[i];
 
        if(new_x < 1 || new_x > n || new_y < 1 || new_y > m) continue;
        if(blocks[new_x][new_y]) continue;
 
        bool hurt = false;
        for(int j = 0; j < l; j++)
        {
            if(snake_x[j] == new_x && snake_y[j] == new_y) hurt = true;
        }
        if(hurt) continue;
  
        int tempx = snake_x[(h-1+l)%l], tempy = snake_y[(h-1+l)%l];
 
        snake_x[(h-1+l)%l] = new_x;
        snake_y[(h-1+l)%l] = new_y;
 
        int this_time = solve(blocks, (h-1+l)%l, (t-1+l)%l, snake_x, snake_y, total+1);
        if(this_time < result) result = this_time;
 
        snake_x[(h-1+l)%l] = tempx;
        snake_y[(h-1+l)%l] = tempy;
        
 
    }
 
    return result;
}
void Delete(int **blocks, int *snake_x, int *snake_y)
{
    for(int i = 1; i <= n; i++)
    {
        delete [] blocks[i];
    }
 
    delete [] snake_x;
    delete [] snake_y;
}
int main()
{
 
    cin >> n >> m >> l;
    int **blocks = new int*[n+1];
    for(int i = 1; i <= n; i++)
    {
        blocks[i] = new int[m+1]();
    }
 
    int *snake_x = new int[l+1]();
    int *snake_y = new int[l+1]();
    for(int i = 0; i < l; i++)
    {
        cin >> snake_x[i] >> snake_y[i];
    }
 
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        blocks[x][y] = 1;
    }
 
    int steps = solve(blocks, 0, l-1, snake_x, snake_y, 0);
 
    if(steps == INT_MAX) cout << "Impossible" << endl;
    else cout << steps << endl;
 
    Delete(blocks, snake_x, snake_y);
    return 0;
}