naoya_t@topcoder

SRM376 Div1 Easy: Trainyard

過去問, 練習 | 13:08 |

たらたらとBFSコーディング。こういうのをてきぱきやりたい。

変数名１（ないし２）文字に拘らないほうが良いかもと思った。

それ以前に、コーディングの前に紙と鉛筆使おう。混乱するぐらいなら。

class Trainyard {
  bool ns(int c){return (c=='.'||c=='-')?false:true;}
  bool ew(int c){return (c=='.'||c=='|')?false:true;}
 public:
  int reachableSquares(vector<string> lo, int fuel) {
    int w=sz(lo[0]),h=sz(lo);
    int sx,sy;
    vector<vector<int> > r(h);
    vector<vector<bool> > v(h);
    rep(y,h){r[y].resize(w); v[y].resize(w);}
    rep(y,h)rep(x,w){ r[y][x]=-1; v[y][x]=false; if(lo[y][x]=='S') {sy=y;sx=x;r[y][x]=fuel;} }
    queue<pair<int,int> > q;
    q.push(make_pair(sy,sx));
    while(!q.empty()){
      int y=q.front().first, x=q.front().second;
      v[y][x]=true; int r_=r[y][x];
      q.pop();
      if(r_<=0) continue;

      int c=lo[y][x];
      if(ns(c)){
        if(y>0){
          if(ns(lo[y-1][x])&&!v[y-1][x]) {r[y-1][x]=r_-1; q.push(make_pair(y-1,x));}
        }
        if(y<h-1){
          if(ns(lo[y+1][x])&&!v[y+1][x]) {r[y+1][x]=r_-1; q.push(make_pair(y+1,x));}
        }
      }
      if(ew(c)){
        if(x>0){
          if(ew(lo[y][x-1])&&!v[y][x-1]) {r[y][x-1]=r_-1; q.push(make_pair(y,x-1));}
        }
        if(x<w-1){
          if(ew(lo[y][x+1])&&!v[y][x+1]) {r[y][x+1]=r_-1; q.push(make_pair(y,x+1));}
        }
      }
    }
    int cnt=0;
    rep(y,h)rep(x,w) if(r[y][x]>=0)cnt++;
    return cnt;
  }
};