Aizu - 0558 Cheese（BFS）

本文主要是介绍Aizu - 0558 Cheese（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

 

    在H * W的地图上有N个奶酪工厂，每个工厂分别生产硬度为1-N的奶酪。有一只老鼠准备从出发点吃遍每一个工厂的奶酪。老鼠有一个体力值，初始时为1，每吃一个工厂的奶酪体力值增加1（每个工厂只能吃一次），且老鼠只能吃硬度不大于当前体力值的奶酪。 

    老鼠从当前格到上下左右相邻的无障碍物的格需要时间1单位，有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪，吃奶酪时间不计。问吃遍所有奶酪最少用时。 

 

输入

第一行三个整数H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9)，之后H行W列为地图， “.“为空地， ”X“为障碍物，”S“为老鼠洞， 1-N代表硬度为1-N的奶酪的工厂。

 

输出

最少用时。

 

样例输入

 

3 3 1
S..
...
..1

4 5 2
.X..1
....X
.XX.S
.2.X.

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

 

 

样例输出

 

4

12

91

 

 

#include<iostream>
#include<queue>
#include<cstring>
#include<stdio.h>
using namespace std;struct Node
{int x,y;
};char c;
int H,W,N;
int dis;
int move[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
int flag[1005][1005];
int d[1005][1005];
char pic[1005][1005];
int fac[12][2];
queue<Node> q;int main()
{while (scanf("%d%d%d",&H,&W,&N)!=EOF){memset(d,0,sizeof(d));memset(flag,0,sizeof(flag));dis = 0;for (int i = 0; i < H; i++){for (int j = 0; j < W; j++){cin >> c;pic[i][j] = c;int num=c-'0';if(c=='S'){fac[0][0]=i;fac[0][1]=j;}if(num<=9&&num>=1){fac[num][0]=i;fac[num][1]=j;}}}Node start={fac[0][0],fac[0][1]};q.push(start);for(int i=0; i<N; i++){while(!q.empty()){Node u=q.front();q.pop();if (u.x==fac[i+1][0]&&u.y==fac[i+1][1]){dis+=d[u.x][u.y];while(!q.empty())q.pop();memset(d,0,sizeof(d));memset(flag,0,sizeof(flag));Node w={fac[i+1][0],fac[i+1][1]};q.push(w);break;}for(int i=0; i<4; i++){int tempx,tempy;tempx=u.x+move[i][0];tempy=u.y+move[i][1];if(tempx<H&&0<=tempx&&tempy<W&&0<=tempy&&pic[tempx][tempy]!='X'&&flag[tempx][tempy]!=1){flag[tempx][tempy]=1;Node v={tempx,tempy};d[tempx][tempy]=d[u.x][u.y]+1;q.push(v);}}}}printf("%d\n",dis);}return 0;
}

 

 

 

 

 

 

这篇关于Aizu - 0558 Cheese（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---