|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 ForTest 於 2014-4-21 08:07 編輯
題目: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]);
}
}
|
評分
-
查看全部評分
|