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; }