読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 2492: goto busters

問題リンク:goto busters | Aizu Online Judge

問題概要:
N行(1 <= N <= 100)のgoto文かlabel文が与えられる。プログラムを正しく動作させるために必要な削除しなくてはならないgoto文の数を出力せよ。

使用した言語:C++

解法;
グラフ化して最短経路をもとめる
・goto文からラベルへのコストは0
・ラベルからラベルの次の行へのコストは0
・goto文から次の行へのコストは1(もしgoto文の次の行が本来のgoto文のラベルなのであれば0)
とする
あとはダイクストラなりフロイド・ワーシャルなりで最短経路をもとめる

※同じラベルは存在しないが同じラベルをもつgoto文は複数存在する可能性がある

コード:

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#include<map>
#include<sstream>
using namespace std;
typedef pair<vector<int>,int> P;

string getVal(string message)
{
  stringstream ss;
  ss << message;
  string a,b;
  ss >> a >> b;
  return b.substr(0,b.size()-1);
}

int main()
{
  int N;
  cin >> N;
  int G[N+1][N+1];
  
  for(int i=0;i<N+1;i++)
    for(int j=0;j<N+1;j++)
      G[j][i] = (1<<29);
  map<string,P> index;
  cin.ignore();
  for(int i=0;i<N;i++)
    {
      string line;
      getline(cin,line);

      if(line.substr(0,4) == "goto")
	index[getVal(line)].first.push_back(i);
      else 	
	index[line.substr(0,line.size()-1)].second = i;
    }

  for(map<string,P>::iterator it = index.begin();it != index.end();it++)
    {
      for(int i=0;i<(*it).second.first.size();i++)
	{
	  G[((*it).second.first)[i]][(*it).second.second] = 0;
	  G[((*it).second.first)[i]][((*it).second.first)[i]+1] = min(G[(*it).second.first[i]][(*it).second.first[i]+1],1);
	}
      G[(*it).second.second][(*it).second.second+1] = 0;
    }

  for(int k=0;k<N+1;k++)
    for(int i=0;i<N+1;i++)
      for(int j=0;j<N+1;j++)
	G[i][j] = min(G[i][j],G[i][k]+G[k][j]);

  cout << G[0][N] << endl;
  return 0;
}