本文链接:http://www.cnblogs.com/Ash-ly/p/5398867.html
题意：
中国和印度之间有一片地方，把这片地方抽象化，于是就可以看成一个N * M矩阵，其中黑色的代表高山不能走过去，白色的代表平原，可以通行,人每次可以选择往上下左右四个方向移动,但是随着时间的变化某些白色的平原会变成黑色的高山，从而变为不可通行，题目中给出一个代表地势的图，然后有 Q 次操作,第 i 次操作 代表在第 i 年 (x, y)处的平原变成了高山,即白色变为了黑色。问中国印度最早彻底断绝的时间,如果在 Q 年后还没有断绝就输出 -1；
思路：
对于0 - Q年份进行二分，然后利用BFS枚举起点判断连通性。如果在mid年时隔绝已经形成，那么说明答案在[lo-mid]之间，继续二分，否则说明答案在(mid,hi]之间。
代码:
#include <stdio.h> #include <string.h> #include <iostream> #include <queue> using namespace std; const int MAXN = 500; int Gra[MAXN + 7][MAXN + 7]; int Date[MAXN + 7][MAXN + 7]; int stpX[] = {1, 0, 0, -1};//下一个状态(方向) int stpY[] = {0, 1, -1, 0}; int visited[MAXN + 7][MAXN + 7];//标记点是否被访问 int n, m; int flag; struct Point{ int x; int y; }pt[MAXN * MAXN + 7]; int chage(int x, int y) { return (x - 1) * m + y; } void BFS()//BFS判断连通性 { memset(visited, 0, sizeof(visited)); queue<Point> ptQu; struct Point pi; for(int i = 1; i <= m ; i++)//枚举起点 { if(Date[1][i] == 1 || visited[1][i]) continue; visited[1][i]= 1; pi.x = 1;pi.y = i; ptQu.push(pi); while(!ptQu.empty()) { pi = ptQu.front(); ptQu.pop(); //cout << pi.x << " " <<pi.y<<endl; if(pi.x == n) {flag = 1;return;} //遍历到了最底下，说明连通 for(int i = 0; i < 4; i++) { int xx = pi.x + stpX[i]; int yy = pi.y + stpY[i]; if(Date[xx][yy] == 0 && !visited[xx][yy]) { visited[xx][yy] = 1; struct Point temp; temp.x = xx, temp.y = yy; ptQu.push(temp); } } } } } int isOk(int mid) { memcpy(Date, Gra, sizeof(Gra)); for(int i = 1; i <= mid; i++) Date[ pt[i].x ][ pt[i].y ] = 1; flag = 0; BFS(); //cout << mid << endl; if(flag) return 0; return 1; } int main() { //freopen("in.txt", "r", stdin); int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n, &m); memset(Gra, -1, sizeof(Gra)); memset(&pt, 0, sizeof(Point)); for(int i = 1; i <= n; i++ ) for(int j = 1; j <= m; j++) scanf("%1d",&Gra[i][j]); int Q; scanf("%d",&Q); for(int i = 1; i <= Q; i++) { int xx, yy; scanf("%d%d", &xx, &yy); pt[i].x = xx + 1; pt[i].y = yy + 1; } int lo =0; int hi = Q; while(lo <= hi)//二分求解 { int mid = (lo + hi) >> 1; if(isOk(mid)) hi = mid - 1; else lo = mid + 1; //printf("%d %d ",lo, hi); } if(hi == Q)printf("-1 "); else printf("%d ", lo); } return 0; }