AOJ 0558 Cheese (BFS分段处理)

题意：这里写链接内容

2019年2月24日

n次bfs，累加求和就可以求得解。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 1010
#define inf 0x3f3f3f
typedef long long ll;
using namespace std;
typedef struct Node{
    int x,y;
}node;
int h,w,n,ans;
int sx,sy,ex,ey;
int d[maxn][maxn];
int dx[4]={
    -1,0,1,0};
int dy[4]={
    0,1,0,-1};
char mp[maxn][maxn];
bool check(int x,int y){
    if(x<0||x>=h||y<0||y>=w)    return false;else return true;
}
int bfs(int sx,int sy,int ex,int ey){
    for(int i=0;i<maxn;i++)for(int j=0;j<maxn;j++) d[i][j]=inf;queue<node> que;node q1,q2,q3;q1.x=sx,q1.y=sy;que.push(q1);d[sx][sy]=0;while(!que.empty()){
    q2=que.front();que.pop();for(int i=0;i<4;i++){
    int nx=q2.x+dx[i];int ny=q2.y+dy[i];if(d[nx][ny]==inf&&mp[nx][ny]!='X'&&check(nx,ny)){
    q3.x=nx,q3.y=ny;que.push(q3);d[nx][ny]=d[q2.x][q2.y]+1;}}}return d[ex][ey];
}void findd(int cur){
    char tmp=cur+'0';       //数字0转换为字符'0'for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
    if(mp[i][j]==tmp){
    ex=i,ey=j;break;}}}
}
int main(){
    std::ios::sync_with_stdio(false);cin>>h>>w>>n;for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
    cin>>mp[i][j];if(mp[i][j]=='S'){
    sx=i,sy=j;}}}for(int i=1;i<=n;i++){
    findd(i);ans+=bfs(sx,sy,ex,ey);sx=ex,sy=ey;}cout<<ans<<endl;return 0;
}

#include<iostream>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define maxn 1010ll h,w,n,sx,sy,ex,ey,ans=0,d[maxn][maxn];
ll dir[4][2]={
    -1,0,1,0,0,1,0,-1};
char mp[maxn][maxn];void find(int x){
    x+=1;char tmp=x+'0';			//数字转字符+'0',字符转数字-'0' for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
    if(mp[i][j]==tmp){
    ex=i;ey=j;break;}}}
}
//广搜 
ll bfs(ll sx,ll sy,ll ex,ll ey){
    queue<PII> que;for(int i=0;i<h;i++)for(int j=0;j<w;j++) d[i][j]=inf;d[sx][sy]=0;que.push(PII(sx,sy));while(!que.empty()){
    PII p=que.front(); que.pop();if(p.first==ex&&p.second==ey) break;for(int i=0;i<4;i++){
    ll nx=p.first+dir[i][0];ll ny=p.second+dir[i][1];if(d[nx][ny]==inf &&nx>=0&&nx<h&&ny<w&&mp[nx][ny]!='X'){
    que.push(PII(nx,ny));d[nx][ny]=d[p.first][p.second]+1;}}}return d[ex][ey];
}int main(){
    cin>>h>>w>>n;for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
    cin>>mp[i][j];if(mp[i][j]=='S'){
    sx=i,sy=j;}}}for(int i=0;i<n;i++){
    find(i);// cout<<"sx,sy="<<sx<<sy<<" ex,ey="<<ex<<ey<<endl;ans+=bfs(sx,sy,ex,ey);sx=ex,sy=ey;}	cout<<ans<<endl;return 0;
}