Untitled
unknown
plain_text
a year ago
3.0 kB
3
Indexable
Never
#include<iostream> using namespace std; int T, n, g; int gold[105][2], arr[105][105], visit[105][105]; int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; int r; int kt1 = 0, kt2 = 0; int rear, front; struct toado{ int x, y; }; toado queue[1000000]; void init(){ rear = 0; front = 0; } void push(int x, int y){ queue[rear].x = x; queue[rear].y = y; rear++; } toado pop(){ toado t = queue[front]; front++; return t; } void nhap(){ cin >> n >> g; for(int i = 0; i < g; i ++) { cin >> gold[i][0] >> gold[i][1]; gold[i][0] --; gold[i][1] --; } for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { arr[i][j] = 0; } } for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { cin >> arr[i][j]; } } } void reset() { for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { visit[i][j] = 100000; } } } bool cdk(int x, int y) { if(x >= 0 && x < n && y >= 0 && y < n) return true; return false; } void BFS(int x, int y) { init(); push(x,y); visit[x][y] = 0; while(front < rear) { toado t = pop(); for(int i = 0; i < 4; i ++) { int xx = t.x + dx[i]; int yy = t.y + dy[i]; if(cdk(xx,yy) && arr[xx][yy]) { if(visit[xx][yy]==100000) { push(xx,yy); visit[xx][yy] = visit[t.x][t.y] + 1; } else if(visit[xx][yy] > visit[t.x][t.y] + 1) visit[xx][yy] = visit[t.x][t.y] + 1; } } } } bool check(int x, int y) { for(int i = 0; i < g; i ++) { if(x == gold[i][0] && y == gold[i][1]) return false; } return true; } void in() { kt1 = 0; kt2 = 0; int sav = 0; for(int i = 0; i < g; i ++) { int x = gold[i][0]; int y = gold[i][1]; if(visit[x][y] == 100000) { kt1 ++; } else { kt2++; if(visit[x][y] > sav) sav = visit[x][y]; } } if(kt2 == g) { if(r > sav) r = sav; } } int main() { freopen("input.txt", "r", stdin); cin >> T; for(int tc = 1; tc <= T; tc++) { nhap(); r = 100000; for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { if(check(i,j) && arr[i][j]) { reset(); BFS(i,j); in(); /*cout << r << endl; for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { cout << visit[i][j] << "\t"; } cout << endl; } cout << endl << endl;*/ } } } cout << "Case #" << tc << endl; if(r == 100000) cout << -1 << endl; else cout << r << endl; } return 0; } 3 5 2 4 3 3 4 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 8 2 5 6 6 4 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 3 4 4 3 4 5 6 10 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 Case #1 1 Case #2 2 Case #11 1 4 3 4 5 6 10