OpenJ_Bailian - 4115：鸣人和佐助

鸣人和佐助：bfs

已知一张地图（以二维矩阵的形式表示）以及佐助和鸣人的位置。地图上的每个位置都可以走到，只不过有些位置上有大蛇丸的手下，需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉，每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动，每移动一个距离需要花费1个单位时间，打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了，则只可以走到没有大蛇丸手下的位置，不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动，大蛇丸的手下也不移动。请问，鸣人要追上佐助最少需要花费多少时间？
Input：
输入的第一行包含三个整数：M，N，T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200，0 ≤ T < 10
后面是M行N列的地图，其中@代表鸣人，+代表佐助。*代表通路，#代表大蛇丸的手下。
Output：
输出包含一个整数R，代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助，则输出-1。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//<< fixed << setprecision(n)
using namespace std;const int MAX = 210;
int flag[MAX][MAX][15];
char cell[MAX][MAX];
int to[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int N,M,T;
struct Pos
{int x,y;int step;int t;Pos(int xx,int yy,int ss,int tt) : x(xx),y(yy),step(ss),t(tt){}
};queue<Pos> q;int main()
{cin >> N >> M >> T;getchar();for(int i = 0;i < MAX ;i++){fill(cell[i],cell[i]+MAX,'%');}for(int i = 1;i <= N;i++){//char *p = cell[i]+1;cin.getline(cell[i]+1,M+1);cell[i][M+1] = '%';}int sx,sy,ex,ey;for(int i = 1;i <= N;i++){for(int j = 1;j <= M;j++){if(cell[i][j] == '@'){sx = i;sy = j;}if(cell[i][j] == '+'){ex = i;ey = j;}}}q.push(Pos(sx,sy,0,T));flag[sx][sy][T] = 1;while(!q.empty()){Pos temp = q.front();if(temp.x == ex && temp.y == ey){//cout << "ans: " << temp.x << " " << temp.y << " " << temp.step << " " << temp.t << endl;cout << temp.step << endl;break;}int tx,ty;for(int i = 0;i < 4;i++){tx = temp.x + to[i][0];ty = temp.y + to[i][1];if(cell[tx][ty] != '%'){if(cell[tx][ty] == '#' && temp.t > 0 && !flag[tx][ty][temp.t-1]){q.push(Pos(tx,ty,temp.step+1,temp.t-1));//cout << "push: " << tx << " " << ty << " " << temp.step+1 << " " << temp.t -1<< endl;flag[tx][ty][temp.t-1] = 1;}else if(cell[tx][ty] != '#' && !flag[tx][ty][temp.t]){q.push(Pos(tx,ty,temp.step+1,temp.t));//cout << "push: " << tx << " " << ty << " " << temp.step+1 << " " << temp.t<< endl;flag[tx][ty][temp.t] = 1;}}}//cout << "pop: " << temp.x << " " << temp.y << " " << temp.step << " " << temp.t << endl;q.pop();}if(q.empty()) cout << "-1";return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！