解いた問題のソースコードと解説など。


SRM 576 Div1 Easy ArcadeManao

問題

2Dゲームの画面が与えられる。'X'で表されるセルが足場を示しており、最下段は全て足場になっている。垂直に位置する2つの足場は、その2つの間の距離以上の長さを持つはしごを使って行き来することができる。最下段から目的地(coinsColumn, coinsRow)まで辿り着くのに必要な最短のはしごの長さを求めよ。

やりかた

はしごの長さを0から2D画面の高さ - 1まで順次変えていき、その時のはしごの長さで最下段から目的地にたどり着けるかを毎回ダイクストラ法で調べていく。初めてたどり着けるはしごの長さになった時、それが答え。

以下ソース。

struct edge {
  int from/*自分*/, to/*行き先*/, flow/*流量*/, cost/*費用*/;
  edge(int from, int to, int flow, int cost) :
    from(from), to(to), flow(flow), cost(cost) {}
  edge(int to, int cost) :
    to(to), cost(cost) {}
  bool operator >(const edge &e) const{
    return cost > e.cost;
  }
  bool operator <(const edge &e) const{
    return cost < e.cost;
  }
};

typedef vector<vector<edge> > Graph;
typedef pair<int, int> P;

int dist[10000];

class ArcadeManao {
public:
  void dijkstra(const Graph &g, int s){
    int V = g.size();
    fill(dist, dist + V, INF);
    dist[s] = 0;
    priority_queue<P, vector<P>, greater<P> > Q;
    Q.push(P(0, s));
    while(!Q.empty()){
      P p = Q.top(); Q.pop();
      int v = p.second;
      if(dist[v] < p.first) continue;
      for(int i = 0; i < (int)g[v].size(); i++){
	edge e = g[v][i];
	if(dist[e.to] > dist[v] + e.cost){
	  dist[e.to] = dist[v] + e.cost;
	  Q.push(P(dist[e.to], e.to));
	}
      }
    }
  }

  int shortestLadder(vector <string> level, int coinRow, int coinColumn) {
    fill(dist, dist + 10000, INF);
    int N = level.size();
    int M = level[0].length();
    
    for(int i = 0; i < N; i++){
      Graph g;
      g.resize(N * M);
      for(int y = 0; y < N; y++){
	for(int x = 0; x < M; x++)if(level[y][x] == 'X'){
	  for(int h = 0; h <= i; h++)
            //はしごで垂直に行き来できるか
	    if(y + h < N && level[y + h][x] == 'X'){
	      g[y * M + x].push_back(edge(y * M + x, (y + h) * M + x, 0, h));
	      g[(y + h) * M + x].push_back(edge((y + h) * M + x, y * M + x, 0, h));
	    }
	  }
          //水平に行き来できるか
	  if(x + 1 < M && level[y][x + 1] == 'X'){
	    g[y * M + x].push_back(edge(y * M + x, y * M + x + 1, 0, 0));
	    g[y * M + x + 1].push_back(edge(y * M + x + 1, y * M + x, 0, 0));
	  }  
	}
      }
      dijkstra(g, N * M - 1);
      if(dist[(coinRow - 1) * M + (coinColumn - 1)] != INF)
	return i;
    }
    return -1;
  }
};
しょげないでよBaby 眠れば治る