test/aoj/0558.test.cpp

View this file on GitHub
Last update: 2020-09-30 16:50:39+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558

Depends on

tools/gridbfs.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../tools/gridbfs.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int h,w,n;
  cin>>h>>w>>n;

  vector<string> st(h);
  for(int i=0;i<h;i++) cin>>st[i];

  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      if(st[i][j]=='S') st[i][j]='0';

  vector<int> ys(n+1),xs(n+1);
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(!isdigit(st[i][j])) continue;
      int p=st[i][j]-'0';
      ys[p]=i;xs[p]=j;
    }
  }

  int ans=0;
  for(int k=0;k<n;k++)
    ans+=gridbfs(st,ys[k],xs[k],'X',4)[ys[k+1]][xs[k+1]];

  cout<<ans<<endl;
  return 0;
}

#line 1 "test/aoj/0558.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "tools/gridbfs.cpp"

#line 3 "tools/gridbfs.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
vector< vector<int> >
gridbfs(vector<string> &st,int sy,int sx,char wall,int dir){
  int h=st.size(),w=st.front().size();
  vector<vector<int> > dp(h,vector<int>(w,-1));
  using P = pair<int, int>;
  queue<P> qu;

  dp[sy][sx]=0;
  qu.emplace(sy,sx);

  int dy[]={1,-1,0,0,1,1,-1,-1};
  int dx[]={0,0,1,-1,1,-1,1,-1};
  auto in=[&](int y,int x){return 0<=y and y<h and 0<=x and x<w;};

  while(!qu.empty()){
    int y,x;
    tie(y,x)=qu.front();qu.pop();
    for(int k=0;k<dir;k++){
      int ny=y+dy[k],nx=x+dx[k];
      if(!in(ny,nx) or st[ny][nx]==wall) continue;
      if(~dp[ny][nx]) continue;
      dp[ny][nx]=dp[y][x]+1;
      qu.emplace(ny,nx);
    }
  }

  return dp;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/0558.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int h,w,n;
  cin>>h>>w>>n;

  vector<string> st(h);
  for(int i=0;i<h;i++) cin>>st[i];

  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      if(st[i][j]=='S') st[i][j]='0';

  vector<int> ys(n+1),xs(n+1);
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(!isdigit(st[i][j])) continue;
      int p=st[i][j]-'0';
      ys[p]=i;xs[p]=j;
    }
  }

  int ans=0;
  for(int k=0;k<n;k++)
    ans+=gridbfs(st,ys[k],xs[k],'X',4)[ys[k+1]][xs[k+1]];

  cout<<ans<<endl;
  return 0;
}