1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
|
My code is:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
void adjacencyList(vector<vector<int> > &adjList, map<int,int> &snake, map<int,int> &ladder){
for(int i=1; i<=100;i++){
for(int j=1;j<=6;j++){
int val = i+j;
if(ladder.find(val) != ladder.end()){
val = ladder.find(val)->second;
}
if(snake.find(val)!= snake.end()){
val = snake.find(val)->second;
}
if(val<=100){
adjList[i][j]= val;
}
else{
adjList[i][j]=0;
}
}
}
}
void breadthFirstSearch(vector<vector<int> > &adjList, int &level){
vector<int> levels;
vector<int> parent;
//cout <<"Inside breadthFirstSearch"<<endl;
levels.resize(101);
parent.resize(101);
for(int i=1;i<=100;i++){
levels[i] = -1;
parent[i] = 0;
}
int lev = 0;
levels[1]=0;
bool flag=1;
//cout <<"Before for loop"<<endl;
while(flag){
flag=0;
for(int i=1;i<=100;i++){
if(levels[i]==lev){
flag = 1;
//cout <<"adjList size is"<<adjList[i].size()<<endl;
for(int j=1;j<=adjList[i].size();j++){
if(parent[adjList[i][j]]== 0){
levels[adjList[i][j]] = lev+1;
parent[adjList[i][j]] = i;
}
}
}
}
lev++;
}
/*cout <<"After for loop"<<endl;
for(int i=1;i<=100;i++){
cout <<"i is "<<i<<", level is "<<levels[i]<<endl;
}
*/cout <<levels[100]<<endl;
}
void printAdjList(vector<vector<int> > &adjList){
cout <<"Inside printAdjList"<<endl;
for(int i=1; i<=100;i++){
cout<<"List "<<i<<" is:";
for(int j=1;j<=6;j++){
cout<<adjList[i][j]<<" -> ";
}
cout<<endl;
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T,N,M,A,B,ans; // T testcase, N ladders, M snakes
map<int,int> ladder;
map<int,int> snake;
vector<vector<int> > adjList;
adjList.resize(101);
for(int i=0;i<=100;i++){
adjList[i].resize(6);
}
cin >>T;
while(T){
cout << "T is "<<T<<endl;
cin >>N;
for(int i=0; i<=100;i++){
adjList[i].clear();
}
cout << "After vector clear "<<endl;
ladder.clear();
snake.clear();
cout << "After map clear "<<endl;
adjList.resize(101);
for(int i=0;i<=100;i++){
adjList[i].resize(6);
}
cout << "N is "<<N<<endl;
while(N){
cin>>A>>B;
ladder[A]=B;
N--;
}
cin >>M;
while(M){
cin >> A >> B;
snake[A]=B;
M--;
}
adjacencyList(adjList,snake,ladder);
//printAdjList(adjList);
breadthFirstSearch(adjList,ans);
T--;
//cout << ans<<endl;
}
return 0;
}
|