/* 分析:BFS。 每个格子需要记录三个数据,横纵 坐标,以及查克拉数量, 如果当前查克拉数量,不超过之前经过时的查克拉数量,那就不用走这一步,否则,仍然可以继续走。 */ #include<iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int maxn = 210; char g[maxn][maxn]; int G[maxn][maxn]; int m, n, w; int sr,sc; int er, ec; int ans=0; int dr[4] = {0, 1, 0, -1};//四个方向 int dc[4] = {1, 0, -1, 0}; struct Node { int r, c, w, t; Node(int r, int c, int w, int t) : r(r), c(c), w(w), t(t) {} }; void BFS() { queue<Node>que; que.push(Node(sr,sc,w,0)); G[sr][sc]=w; while(que.size()) { Node h=que.front(); que.pop(); if(h.r==er && h.c==ec) { ans=h.t; break; } for(int i=0;i<4;i++) { int dx=h.r+dr[i]; int dy=h.c+dc[i]; if(dx>=0 && dy>=0 && dx<m &&dy<n && G[dx][dy]<h.w) { if(g[dx][dy]=='#' && h.w>0) { que.push(Node(dx,dy,h.w-1,h.t+1)); G[dx][dy]=h.w-1; } else if (g[dx][dy]=='+'||g[dx][dy]=='*') { que.push(Node(dx,dy,h.w,h.t+1)); G[dx][dy]=h.w; } } } } } int main() { cin>>m>>n>>w; for(int i = 0; i < m; i++) { scanf("%s", g[i]); for(int j = 0; j < n; j++) { G[i][j] = -1; //每个格子的查克拉数量初始化为-1, //因为鸣人没有查克拉的时候 (即为0),依然可以走这个格子 if(g[i][j] == '@') sr = i, sc = j; if(g[i][j] == '+') er = i, ec = j; } } BFS(); if(ans != 0) printf("%d\n", ans); else printf("-1"); return 0; }