KangarooCommotion

The input consists of:

• A line containing three integers r, c (1 ≤ r, c ≤ 50), the number of rows and columns of the grid, and k (1 ≤ k ≤ 5), the number of other kangaroos you need to warn.

• r lines each consisting of c characters. A “.” indicates an open space and a “#” indicates a bush where you can’t jump.

Your start position is indicated by a “0” and the characters “1” to k indicate the positions of the other kangaroos you need to warn in this order.

The position indicated by k+ 1 indicates the safe area where you should come to a stop.

C++(clang++11) 解法, 执行用时: 341ms, 内存消耗: 105044K, 提交时间: 2021-04-11 20:54:10

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
const int N = 51;
const int B = 10;
using namespace std;
struct node{int x,y,vx,vy,p;};
int n,m,k,x0,y0,dis[N][N][N<<1][N<<1][8];
int dx[]={-1,0,1,-1,0,1,-1,0,1};
int dy[]={-1,-1,-1,0,0,0,1,1,1};
char M[N][N];queue<node>qe;
int main(){
 scanf("%d%d%d",&n,&m,&k);getchar();
 for(int i = 1;i <= n;i ++){
  for(int j = 1;j <= m;j ++){
   scanf("%c",&M[i][j]);
   if(M[i][j] == '0')x0=i,y0=j;
  }
  getchar();
 }
 dis[x0][y0][0+B][0+B][0]=1;
 qe.push((node){x0,y0,0,0,0});
 while(!qe.empty()){
  node u = qe.front();qe.pop();
  for(int i = 0;i < 9;i ++){
   int nx = u.vx + dx[i],ny = u.vy + dy[i];
   int X = u.x+nx,Y = u.y+ny,f=0;
   if(X<1||Y<1||X>n||Y>m)continue;
   if(nx<-B||nx>B||ny<-B||ny>B)continue; 
   if(M[X][Y] == '#')continue;
    if(M[X][Y]-'0'==u.p+1)f=1;
   if(dis[X][Y][nx+B][ny+B][u.p+f])continue;
   dis[X][Y][nx+B][ny+B][u.p+f]=dis[u.x][u.y][u.vx+B][u.vy+B][u.p]+1;
   if(!nx&&!ny&&u.p+f==k+1&&M[X][Y]-'0'==k+1){printf("%d\n",dis[X][Y][nx+B][ny+B][u.p+f]-1);return 0;}
   qe.push((node){X,Y,nx,ny,f+u.p});
  }
 }puts("impossible");
 return 0;
}

详情