迷宫求最短路的话一般用bfs都可以解决，但是这个加了个状态，那么就增加一个维度，用来判断k的值。比较简单的三维bfs。写搜索题的话一定要注意细节。这个题花了好长的时间。因为k的原因，一开始用了k的原因，dfs好想一些，因为可以回溯，k的值搜完一个方向，然后回溯。那样就很简单。而且数据是20*20.
但是最后dfs还是T了。
AC的bfs
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
const double Pi=3.14159265358979323846;
typedef long long ll;
const int MAXN=+;
int dx[]={-,,,};
int dy[]={,,,-};
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll mod=1e9+;
int vis[][][];
int M[][];
int m,n;
struct node{
int x,y,step,k;
node (int x=,int y=,int step=,int k=)
{
this->x=x;
this->y=y;
this->step=step;
this->k=k;
}
}tim,now;
int bfs(int x,int y,int k)
{
queue <node> Q;
Q.push(node(,,,k));
vis[][][k]=;
while(!Q.empty())
{
tim=Q.front();Q.pop();
if(tim.x==m&&tim.y==n)
{
return tim.step;
}
for(int i=;i<;i++)
{
now.x=dx[i]+tim.x;
now.y=dy[i]+tim.y;
if(M[now.x][now.y]==) now.k=tim.k-;
else now.k=k;
if(now.x>=&&now.x<=m&&now.y>=&&now.y<=n&&(M[now.x][now.y]==||now.k>=)&&!vis[now.x][now.y][now.k])
{
now.step=tim.step+;
Q.push(now);
//cout << now.x<<" "<< now.y<< " "<< now.step<<endl;
vis[now.x][now.y][now.k]=;
}
}
}
return -;
}
int main()
{
int t;cin>>t;
while(t--)
{
cin>>m>>n;
int k;cin>>k;
memset(vis,,sizeof(vis));
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
cin>>M[i][j];
cout <<bfs(,,k)<<endl;
}
return ;
}
TLE的dfs
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
const double Pi=3.14159265358979323846;
typedef long long ll;
const int MAXN=+;
int dx[]={-,,,};
int dy[]={,,,-};
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll mod=1e9+;
int m,n;
int vis[][];
int M[][];
int step[][];
int ans=INF;
int tk;
void dfs(int x,int y,int k)
{
if(x==m&&y==n)
{
if(ans>step[x][y])
ans=step[x][y];
return;
}
for(int i=;i<;i++)
{
int sx=dx[i]+x;
int sy=dy[i]+y;
if(sx>=&&sx<=m&&sy>=&&sy<=n&&!vis[sx][sy]&&(k>||M[sx][sy]==))
{
int pk=k;
if(M[sx][sy]==) pk--;
else pk=tk;
vis[sx][sy]=;
step[sx][sy]=step[x][y]+;
dfs(sx,sy,pk);
vis[sx][sy]=;
}
}
}
int main()
{
int t;cin>>t;
while(t--)
{
ans=INF;
memset(vis,,sizeof(vis));
memset(step,-,sizeof(step));
cin>>m>>n;cin>>tk;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
cin>>M[i][j];
step[][]=;
vis[][]=;
dfs(,,tk);
if(step[m][n]!=-) cout <<ans<<endl;
else cout <<-<<endl;
}
return ;
}