Submission #2869526

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<int,int> P;

const int MAX_H = 50;
const int MAX_W = 50;

ll w,h;
char s[MAX_H][MAX_W];
ll dist[MAX_H][MAX_W];
int dx[4] = {1,-1,0,0}, dy[4] = {0,0,-1,1};
ll white_cnt = 0;

ll bfs(){
  queue<P> que;
  cin >> h >> w;
  REP(i,h){
    REP(j,w){
      cin >> s[i][j];
      dist[i][j] = INF;
      if(s[i][j]=='.') white_cnt++;
    }
  }
  que.push(P(0,0));
  dist[0][0] = 0;
  while(que.size()){
    P p = que.front(); que.pop();
    if(p.first==h-1&&p.second==w-1) break;
    REP(i,4){
      int ny = p.first+dy[i];
      int nx = p.second+dx[i];
      if(ny>=0&&ny<h&&nx>=0&&nx<w&&s[ny][nx]!='#'&&dist[ny][nx]==INF){
        dist[ny][nx] = dist[p.first][p.second]+1;
        que.push(P(ny,nx));
      }
    }
  }
  return dist[h-1][w-1];
}

int main(){
  ll min_dist = bfs();
  if(min_dist==INF){
    cout << -1 << endl;
  }else{
    cout << white_cnt-min_dist-1 << endl;
  }
  return 0;
}

Submission Info

Judge Result