题目： 

思路：

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
char g[N][N];//输入：图的数组
int vis[N][N];
/*
剪枝：记录magic的个数（一个点经过两次，magic越大越好，如果第一次magic
大于第二次，则无需经过第二次*/
struct node
{int x,y,step,magic;
};
int n,k;
int nex[4][2]={{0,1},{0,-1},{-1,0},{1,0}};signed main()
{cin>>n>>k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cin>>g[i][j];}memset(vis,-1,sizeof(vis));queue<node> que;vis[1][1]=0;que.push({ 1,1,0,0});while(que.size()){node t=que.front();que.pop();if(t.x==n&&t.y==n){cout<<t.step;return 0;}for(int i=0;i<4;i++){//获取上下左右的坐标int tx=t.x+nex[i][0];int ty=t.y+nex[i][1];if(g[tx][ty]=='X'&&t.magic==0)continue;int magic=max(0,t.magic-1);if(g[tx][ty]=='%')magic=k;if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&vis[tx][ty]<magic&&g[tx][ty]!='#'){vis[tx][ty]=magic;que.push({tx,ty,t.step+1,magic});}}}cout<<-1;return 0;
}

模板：

char g[N][N];//输入：图的数组
int vis[N][N];//标志数组or剪枝数组
/*
剪枝：记录magic的个数（一个点经过两次，magic越大越好，如果第一次magic
大于第二次，则无需经过第二次*/
struct node//定义一个结构体
{int x,y,step,magic;//属性
};
//上下左右方向数组
int nex[4][2]={{0,1},{0,-1},{-1,0},{1,0}};signed main()
{//输入和数组初始化vis[1][1]=0;//定义类型为结构体的队列queue<node> que;//第一个元素入队(结构体要加{}）que.push({ 1,1,0,0});//循环条件队列不为空while(que.size()){//获取队首元素node t=que.front();que.pop();//终止条件(到达终点）if(t.x==n&&t.y==n){cout<<t.step;return 0;}//枚举所有可能的坐标，并对每一个坐标不同的情形进行判断for(int i=0;i<4;i++){ 	   //获取上下左右的坐标int tx=t.x+nex[i][0];int ty=t.y+nex[i][1];if(g[tx][ty]=='X'&&t.magic==0)continue;int magic=max(0,t.magic-1);if(g[tx][ty]=='%')magic=k;if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&vis[tx][ty]<magic&&g[tx][ty]!='#'){vis[tx][ty]=magic;que.push({tx,ty,t.step+1,magic});//新元素入队}}}cout<<-1;return 0;
}