首页 > 代码库 > BFS AOJ 0558 Chess

BFS AOJ 0558 Chess

AOJ 0558 Chess http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558

      在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的奶酪的工厂。输出最少用时。 。

样例输入:

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

样例输出:

12
#include<iostream>#include<queue>using namespace std;typedef struct{ int x; int y;}P;//表示坐标char graph[1000][1000];P aim[10];P s,g;//s起点,g终点int N,W,H;int vis[1000][1000]; //用来存储距离int dx[]={1,0,-1,0},dy[]={0,1,0,-1};int bfs(P s,P g);int main(){    int i,j,t,step=0;    cin>>H>>W>>N;        for(i=0;i<H;i++)    for(j=0;j<W;j++){        cin>>graph[i][j];      if(graph[i][j]<=9&&graph[i][j]>=1){          t=graph[i][j]-0;         aim[t].x=i;         aim[t].y=j;      } //把1-N的坐标保存在 aim数组中       else if(graph[i][j]==S){          s.x=i;          s.y=j;          graph[i][j]=.;      }//得到最初的起点     }        for(i=1;i<=N;i++){       g.x=aim[i].x;       g.y=aim[i].y;//1-N ,从小到大,每次把一个 作为终点        step+=bfs(s,g);       s.x=g.x;       s.y=g.y;//到达这个终点后变终点为起点        graph[g.x][g.y]=.;    }       cout<<step<<endl;}int bfs(P s,P g){    queue<P> que;      P n;        for(int i=0;i<H;i++)    for(int j=0;j<W;j++)     vis[i][j]=-1;          que.push(s);     vis[s.x][s.y]=0;          while(que.size()){                P p=que.front();         que.pop();       if(p.x==g.x&&p.y==g.y)       break;              for(int i=0;i<4;i++){           n.x=p.x+dx[i];           n.y=p.y+dy[i];//向四方漫射         if(0<=n.x&&n.x<H&&0<=n.y&&n.y<W&&graph[n.x][n.y]!=X&&vis[n.x][n.y]==-1){               que.push(n);               vis[n.x][n.y]=vis[p.x][p.y]+1;           }       }   }     return vis[g.x][g.y];}
 

BFS AOJ 0558 Chess