题目
非常简单的BFS 暴搜
代码语言：javascript复制struct Node
{
int x;
int y;
int k;
int ans;
Node(){}
Node(int x,int y,int k,int ans)
{
this->x=x;
this->y=y;
this->k=k;
this->ans=ans;
}
};
class Solution {
public:
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
int vis[105][105];
int vis2[105][105];
int n,m;
vector<vector<int>> map;
queue<Node> q;
int shortestPath(vector<vector<int>>& grid, int k) {
n = grid.size();
m = grid[0].size();
memset(vis,-1,sizeof(vis));
q.push(Node(0,0,k,0));
int ans = -1;
while(!q.empty())
{
Node term = q.front();
q.pop();
if(term.x == n-1 && term.y==m-1)
{
return term.ans;
}
for(int i=0;i<4;i )
{
int xx = term.x dir[i][0];
int yy = term.y dir[i][1];
if(xx < 0 || yy < 0 || xx >= n || yy >=m)
continue;
if(vis[xx][yy]!=-1&&vis[xx][yy]>=term.k)
continue;
if(grid[xx][yy]==1)
{
if(term.k>0)
{
vis[xx][yy]=term.k-1;
q.push(Node(xx,yy,term.k-1,term.ans 1));
}
}
else
{
vis[xx][yy]=term.k;
q.push(Node(xx,yy,term.k,term.ans 1));
}
}
}
return -1;
}
};
