SRM 376 Div1 easy Trainyard

問題
http://community.topcoder.com/stat?c=problem_statement&pm=6555

各マスについて右と下のセルと連結しているか調べ、連結していれば距離は1、そうでなければINFとする。あとはWarshall-Floydで最短距離を求めて開始点Sからの距離がfuel以下のセルを数える。

ソース

int reachableSquares(vector <string> layout, int fuel) {
    int result = 0;
    int d[200][200];
    for(int i = 0; i < 200; i++){
      for(int j = 0; j < 200; j++){
	d[i][j] = INF;
      }
      d[i][i] = 0;
    }
    int N = layout.size();
    int M = layout[0].size();

    int X, Y;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++)
	if(layout[i][j] == 'S'){
	  X = j, Y = i;
	  layout[i][j] = '+';
	  break;
	}

    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++){
	if(layout[i][j] == '|'){
	  if(i + 1 < N && (layout[i + 1][j] == '|' || layout[i + 1][j] == '+')){
	    d[i * M + j][(i + 1) * M + j] = 1;
	    d[(i + 1) * M + j][i * M + j] = 1;
	  }
	}else if(layout[i][j] == '-'){
	  if(j + 1 < M && (layout[i][j + 1] == '-' || layout[i][j + 1] == '+')){
	    d[i * M + j][i * M + j + 1] = 1;
	    d[i * M + j + 1][i * M + j] = 1;
	  }
	}else if(layout[i][j] == '+'){
	  if(i + 1 < N && (layout[i + 1][j] == '|' || layout[i + 1][j] == '+')){
	    d[i * M + j][(i + 1) * M + j] = 1;
	    d[(i + 1) * M + j][i * M + j] = 1;
	  }
	  if(j + 1 < M && (layout[i][j + 1] == '-' || layout[i][j + 1] == '+')){
	    d[i * M + j][i * M + j + 1] = 1;
	    d[i * M + j + 1][i * M + j] = 1;
	  }
	}
      }

    for(int k = 0; k < 120; k++)
      for(int i = 0; i < 120; i++)
	for(int j = 0; j < 120; j++)
	  d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    for(int i = 0; i < 120; i++)
      if(d[Y * M + X][i] <= fuel) result++;

    return result;
  }

そろそろDiv2 Hard演習に入りたい。