as

/*
分析: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;
}

 

上一篇:P1196 [NOI2002]银河英雄传说


下一篇:函数指针和指针函数