#include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <cmath> #include <cassert> #include <cstring> #include <ext/numeric> #include <bitset> using namespace std ; using namespace __gnu_cxx ; typedef long long LL ; typedef pair<int,int> PII ; typedef vector<int> VI ; const int INF = 1e9+100 ; const LL INFLL = (LL)INF * (LL)INF ; #define REP(i,n) for(i=0;i<(n);++i) #define ALL(c) c.begin(),c.end() #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define CLEAR(t) memset(t,0,sizeof(t)) #define PB push_back #define MP make_pair #define FI first #define SE second template<class T1,class T2> ostream& operator<<(ostream &s, const pair<T1,T2> &x) { s<< "(" << x.FI << "," << x.SE << ")"; return s;} template<class T> ostream& operator<<(ostream &s, const vector<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T> ostream& operator<<(ostream &s, const set<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T1,class T2> ostream& operator<<(ostream &s, const map<T1, T2> &t) { FOREACH(it, t) s << *it << " " ; return s ; } /////////////////////////////////////////// const int MAXN = 200 ; typedef bitset<MAXN> BITSET ; BITSET G[MAXN] ; BITSET goal ; inline void ___try(const BITSET &x, int k) { // cout << k << ") " << x << endl ; if((x&goal)==x) { cout << k << endl ; exit(0) ; } } inline void step(const BITSET &a, int n, BITSET &ret) { ret.reset() ; int i ; REP(i,n) if(a[i]) ret |= G[i] ; } int main() { ios_base::sync_with_stdio(0) ; int n, b, r, i, j, a ; char c ; cin >> n >> b >> r ; REP(i,n) REP(j,n) { cin >> c ; if(c=='1') G[i].set(j) ; } REP(i,b) goal.set(i) ; BITSET start ; while(r--) { cin >> a ; start.set(a-1) ; } ___try(start, 0) ; BITSET p1=start, p2=start ; BITSET tmp ; for(int k=1 ; ; k++) { step(p2, n, tmp) ; ___try(tmp, k) ; k++ ; step(tmp, n, p2) ; ___try(p2, k) ; step(p1, n, tmp) ; p1 = tmp ; if(p2==p1) { // mamy cykl cout << -1 << endl ; return 0 ; } } }
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 | #include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <cmath> #include <cassert> #include <cstring> #include <ext/numeric> #include <bitset> using namespace std ; using namespace __gnu_cxx ; typedef long long LL ; typedef pair<int,int> PII ; typedef vector<int> VI ; const int INF = 1e9+100 ; const LL INFLL = (LL)INF * (LL)INF ; #define REP(i,n) for(i=0;i<(n);++i) #define ALL(c) c.begin(),c.end() #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define CLEAR(t) memset(t,0,sizeof(t)) #define PB push_back #define MP make_pair #define FI first #define SE second template<class T1,class T2> ostream& operator<<(ostream &s, const pair<T1,T2> &x) { s<< "(" << x.FI << "," << x.SE << ")"; return s;} template<class T> ostream& operator<<(ostream &s, const vector<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T> ostream& operator<<(ostream &s, const set<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T1,class T2> ostream& operator<<(ostream &s, const map<T1, T2> &t) { FOREACH(it, t) s << *it << " " ; return s ; } /////////////////////////////////////////// const int MAXN = 200 ; typedef bitset<MAXN> BITSET ; BITSET G[MAXN] ; BITSET goal ; inline void ___try(const BITSET &x, int k) { // cout << k << ") " << x << endl ; if((x&goal)==x) { cout << k << endl ; exit(0) ; } } inline void step(const BITSET &a, int n, BITSET &ret) { ret.reset() ; int i ; REP(i,n) if(a[i]) ret |= G[i] ; } int main() { ios_base::sync_with_stdio(0) ; int n, b, r, i, j, a ; char c ; cin >> n >> b >> r ; REP(i,n) REP(j,n) { cin >> c ; if(c=='1') G[i].set(j) ; } REP(i,b) goal.set(i) ; BITSET start ; while(r--) { cin >> a ; start.set(a-1) ; } ___try(start, 0) ; BITSET p1=start, p2=start ; BITSET tmp ; for(int k=1 ; ; k++) { step(p2, n, tmp) ; ___try(tmp, k) ; k++ ; step(tmp, n, p2) ; ___try(p2, k) ; step(p1, n, tmp) ; p1 = tmp ; if(p2==p1) { // mamy cykl cout << -1 << endl ; return 0 ; } } } |