#include <iomanip> #include <iostream> #include <queue> #include <utility> #include <algorithm> #include <cassert> #include <string> #include <vector> #include <set> #include <map> #include <cstdlib> using namespace std; #define ALL(x) x.begin(), x.end() #define VAR(a,b) __typeof (b) a = b #define REP(i,n) for (int _n=(n), i=0; i<_n; ++i) #define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i) #define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i) #define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) #define IN(x) int x; cin >> x #define PB push_back #define MP make_pair #define ST first #define ND second typedef vector<int> VI; typedef long long LL; typedef pair<int,int> PII; typedef double LD; int n, b, r; vector<string> v, a; VI positions; bool check_init() { FORE(it, positions) if (*it >= b) return false; return true; } bool check_cur() { FORE(it, positions) FOR(i, b, n - 1) if (v[*it][i] == '1') return false; return true; } void advance() { vector<string> new_v; new_v.resize(n); REP(i,n) REP(j,n) new_v[i] += '0'; REP(k, n) REP(i, n) REP(j, n) if (v[i][k] == '1' && a[k][j] == '1') new_v[i][j] = '1'; swap(new_v, v); } int main() { ios_base::sync_with_stdio(0); cout.setf(ios::fixed); cin >> n >> b >> r; v.resize(n); FORE(it,v) cin >> *it; a = v; positions.resize(r); FORE(it, positions) cin >> *it; FORE(it, positions) --*it; if (check_init()) { cout << 0 << endl; return 0; } int MAXK = max((int(1e8) / 4) / (n * n * n), 200); //cout << MAXK << endl; for (int k = 1; k < MAXK; ++k) { if (check_cur()) { cout << k << endl; return 0; } advance(); } cout << -1 << endl; }
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 | #include <iomanip> #include <iostream> #include <queue> #include <utility> #include <algorithm> #include <cassert> #include <string> #include <vector> #include <set> #include <map> #include <cstdlib> using namespace std; #define ALL(x) x.begin(), x.end() #define VAR(a,b) __typeof (b) a = b #define REP(i,n) for (int _n=(n), i=0; i<_n; ++i) #define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i) #define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i) #define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) #define IN(x) int x; cin >> x #define PB push_back #define MP make_pair #define ST first #define ND second typedef vector<int> VI; typedef long long LL; typedef pair<int,int> PII; typedef double LD; int n, b, r; vector<string> v, a; VI positions; bool check_init() { FORE(it, positions) if (*it >= b) return false; return true; } bool check_cur() { FORE(it, positions) FOR(i, b, n - 1) if (v[*it][i] == '1') return false; return true; } void advance() { vector<string> new_v; new_v.resize(n); REP(i,n) REP(j,n) new_v[i] += '0'; REP(k, n) REP(i, n) REP(j, n) if (v[i][k] == '1' && a[k][j] == '1') new_v[i][j] = '1'; swap(new_v, v); } int main() { ios_base::sync_with_stdio(0); cout.setf(ios::fixed); cin >> n >> b >> r; v.resize(n); FORE(it,v) cin >> *it; a = v; positions.resize(r); FORE(it, positions) cin >> *it; FORE(it, positions) --*it; if (check_init()) { cout << 0 << endl; return 0; } int MAXK = max((int(1e8) / 4) / (n * n * n), 200); //cout << MAXK << endl; for (int k = 1; k < MAXK; ++k) { if (check_cur()) { cout << k << endl; return 0; } advance(); } cout << -1 << endl; } |