b010 - E.跳跳跳

ForTest

題目：http://judge.tnfsh.tn.edu.tw:8080/ShowProblem?problemid=b010
AC Code：http://ideone.com/nbPoD5

根據題目條件BFS。
/**********************************************************************************/  
/*  Problem: b010 "E.跳跳跳" from 2009 校內初選                                   */  
/*  Language: C++                                                                 */  
/*  Result: AC (46ms, 884KB) on ZeroJudge                                         */  
/*  Author: ForTest at 2013-12-26 09:57:13                                        */  
/**********************************************************************************/  
  
#include <iostream>  
#include <cstdio>  
#include <vector>  
#include <algorithm>  
#include <cstring>  
#include <string>  
#include <cstdlib>  
#include <cmath>  
#include <queue>  
  
using namespace std;  
  
const int Max=201;  
char map[Max][Max];  
int dis[Max][Max];  
int n,m;  
  
struct data{  
    int x,y;  
};  
  
bool In(int x,int y){  
    return x >= 0 && x < n && y >= 0 && y < m;   
}  
  
int dx[]={0,1,0,-1};  
int dy[]={1,0,-1,0};  
  
int main(){  
    while(~scanf("%d%d",&n,&m)){  
        getchar();  
        vector<data>w[5];  
        data s,e;  
        for(int i=0;i<n;++i){  
            for(int j=0;j<m;++j){  
                dis[i][j]=0x7f7f7f7f;  
                scanf("%c",&map[i][j]);  
                  
                char & now = map[i][j];  
                data push = { i , j };  
                  
                if(now >= '1' && now <= '4')w[ now - '0' ].push_back(push);  
                else if(now == 'S'){s.x = i;s.y = j;dis[i][j] = 0;}  
                else if(now == 'E'){e.x = i;e.y = j;}  
            }  
            getchar();  
        }  
        /*for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                putchar(map[i][j]);
            }
            puts("");
        }*/  
        queue<data> q;  
        q.push(s);  
        while(!q.empty()){  
            data now=q.front(); q.pop();  
            if(map[now.x][now.y] >= '1' && map[now.x][now.y] <= '4'){  
                int cnt = map[now.x][now.y] - '0';  
                int plus = dis[now.x][now.y];  
                while(plus % cnt)plus++;  
                for(vector<data>::iterator i = w[cnt].begin();  
                    i != w[cnt].end(); ++i){  
                        if(dis[(*i).x][(*i).y] > plus + 1){  
                            dis[(*i).x][(*i).y] = plus + 1;  
                            q.push(*i);  
                        }  
                    }  
            }  
            for(int i=0;i<4;++i){  
                data next={now.x + dx[i],now.y + dy[i]};  
                if(In(next.x , next.y)){  
                    char & pos = map[next.x][next.y];  
                    int  & d = dis[next.x][next.y];  
                    if(pos != '#' && d > dis[now.x][now.y] + 1){  
                        d = dis[now.x][now.y] + 1;  
                        q.push(next);  
                    }  
                }  
            }  
        }  
        /*for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                printf("%d ",dis[i][j]);
            }
            puts("");
        }*/  
        if(dis[e.x][e.y] == 0x7f7f7f7f)puts("-1");  
        else printf("%d\n",dis[e.x][e.y]);  
    }  
}