fork(1) download
copy 
  1. /**********************************************************************************/  
  2. /*  Problem: b010 "E.跳跳跳" from 2009 校內初選                                   */  
  3. /*  Language: C++                                                                 */  
  4. /*  Result: AC (46ms, 884KB) on ZeroJudge                                         */  
  5. /*  Author: ForTest at 2013-12-26 09:57:13                                        */  
  6. /**********************************************************************************/  
  7.  
  8. #include <iostream>  
  9. #include <cstdio>  
  10. #include <vector>  
  11. #include <algorithm>  
  12. #include <cstring>  
  13. #include <string>  
  14. #include <cstdlib>  
  15. #include <cmath>  
  16. #include <queue>  
  17.  
  18. using namespace std;  
  19.  
  20. const int Max=201;  
  21. char map[Max][Max];  
  22. int dis[Max][Max];  
  23. int n,m;  
  24.  
  25. struct data{  
  26.     int x,y;  
  27. };  
  28.  
  29. bool In(int x,int y){  
  30.     return x >= 0 && x < n && y >= 0 && y < m;   
  31. }  
  32.  
  33. int dx[]={0,1,0,-1};  
  34. int dy[]={1,0,-1,0};  
  35.  
  36. int main(){  
  37.     while(~scanf("%d%d",&n,&m)){  
  38.         getchar();  
  39.         vector<data>w[5];  
  40.         data s,e;  
  41.         for(int i=0;i<n;++i){  
  42.             for(int j=0;j<m;++j){  
  43.                 dis[i][j]=0x7f7f7f7f;  
  44.                 scanf("%c",&map[i][j]);  
  45.  
  46.                 char & now = map[i][j];  
  47.                 data push = { i , j };  
  48.  
  49.                 if(now >= '1' && now <= '4')w[ now - '0' ].push_back(push);  
  50.                 else if(now == 'S'){s.x = i;s.y = j;dis[i][j] = 0;}  
  51.                 else if(now == 'E'){e.x = i;e.y = j;}  
  52.             }  
  53.             getchar();  
  54.         }  
  55.         /*for(int i=0;i<n;++i){ 
  56.             for(int j=0;j<m;++j){ 
  57.                 putchar(map[i][j]); 
  58.             } 
  59.             puts(""); 
  60.         }*/  
  61.         queue<data> q;  
  62.         q.push(s);  
  63.         while(!q.empty()){  
  64.             data now=q.front(); q.pop();  
  65.             if(map[now.x][now.y] >= '1' && map[now.x][now.y] <= '4'){  
  66.                 int cnt = map[now.x][now.y] - '0';  
  67.                 int plus = dis[now.x][now.y];  
  68.                 while(plus % cnt)plus++;  
  69.                 for(vector<data>::iterator i = w[cnt].begin();  
  70.                     i != w[cnt].end(); ++i){  
  71.                         if(dis[(*i).x][(*i).y] > plus + 1){  
  72.                             dis[(*i).x][(*i).y] = plus + 1;  
  73.                             q.push(*i);  
  74.                         }  
  75.                     }  
  76.             }  
  77.             for(int i=0;i<4;++i){  
  78.                 data next={now.x + dx[i],now.y + dy[i]};  
  79.                 if(In(next.x , next.y)){  
  80.                     char & pos = map[next.x][next.y];  
  81.                     int  & d = dis[next.x][next.y];  
  82.                     if(pos != '#' && d > dis[now.x][now.y] + 1){  
  83.                         d = dis[now.x][now.y] + 1;  
  84.                         q.push(next);  
  85.                     }  
  86.                 }  
  87.             }  
  88.         }  
  89.         /*for(int i=0;i<n;++i){ 
  90.             for(int j=0;j<m;++j){ 
  91.                 printf("%d ",dis[i][j]); 
  92.             } 
  93.             puts(""); 
  94.         }*/  
  95.         if(dis[e.x][e.y] == 0x7f7f7f7f)puts("-1");  
  96.         else printf("%d\n",dis[e.x][e.y]);  
  97.     }  
  98. }
Success #stdin #stdout 0s 3496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nbPoD5
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!