0558:Cheese

スタート地点と1~nのチーズがおいてあるグリッドが与えられるので
チーズを順番に取っていったときの最短経路の長さを求める問題。

幅優先探索でiとi+1の間の最短経路をそれぞれ求めた。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

#define mp make_pair
#define f first
#define s second

using namespace std;

typedef pair<int,int> P;

const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int h,w;
string grid[1000];
int d[1000][1000];

void bfs(P S){

  queue<P>que;
  que.push(S);
  d[S.f][S.s]=0;

  while(!que.empty()){
    P now=que.front();
    
    que.pop();
    for(int i=0;i<4;i++){
      if(0<=now.f+dx[i] && 0<=now.s+dy[i] &&
	 now.f+dx[i]<h && now.s+dy[i]<w
	 && grid[now.f+dx[i]][now.s+dy[i]]!='X'){

	if(d[now.f][now.s]+1<d[now.f+dx[i]][now.s+dy[i]]){
	  d[now.f+dx[i]][now.s+dy[i]]=d[now.f][now.s]+1;
	  que.push(P(now.f+dx[i],now.s+dy[i]));
	}
      }
    }
  }
}

int main(void){
  int n;
  P v[1001];

  cin >> h >> w >> n;

  for(int i=0;i<h;i++)cin >> grid[i];

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(grid[i][j]=='S')v[0]=mp(i,j);
      if(grid[i][j]!='X'&&grid[i][j]!='.')
	v[grid[i][j]-'0']=mp(i,j);
    }
  }

  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<h;j++)
      for(int k=0;k<w;k++)d[j][k]=100000000;
    bfs(v[i]);
    ans+=d[v[i+1].f][v[i+1].s];
  }

  cout << ans << endl;

  return 0;
}