Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2208 Accepted Submission(s): 838
/***** 题意:给出一个矩阵,然后给出两个点,让求链接这两个点需要打的洞的最小值 ‘.’代表空位置,‘X’代表是洞; 做法:bfs + 优先队列 *****/ #include<iostream> #include<string.h> #include<algorithm> #include<cmath> #include<stdio.h> #include<queue> using namespace std; #define maxn 1100 #define INF 1000000 int Edge[maxn][maxn]; char ch[maxn][maxn]; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0,}; int n,m; int temp = 0; int sx,sy,ex,ey; int vis[maxn][maxn]; struct Node { int x; int y; int step; Node() { x = 0; y = 0; step =0; } }; struct cmp { bool operator () (const Node &a,const Node &b) { return a.step>b.step; } }; int check(Node a) { if(a.x >= 1 && a.x <=n && a.y>=1 && a.y <=m) return 1; return 0; } priority_queue<Node,vector<Node>,cmp >que; int bfs() { while(!que.empty()) que.pop(); Node now,tmp; now.x = sx; now.y = sy; now.step = 0; que.push(now); vis[sx][sy] = 1; while(!que.empty()) { tmp = que.top(); que.pop(); if(tmp.x == ex && tmp.y == ey) return tmp.step; for(int i=0; i<4; i++) { now.x = tmp.x + dx[i]; now.y = tmp.y + dy[i]; if(check(now) && vis[now.x][now.y] == 0) { if(Edge[now.x][now.y] == 0) now.step = tmp.step; else { now.step = tmp.step + 1; } que.push(now); vis[now.x][now.y] = 1; } } } } int main() { //#ifndef ONLINE_JUDGE // freopen("in1.txt","r",stdin); //#endif while(~scanf("%d %d",&n,&m)) { if(n == 0 && m == 0) break; memset(Edge,INF,sizeof(Edge)); memset(vis,0,sizeof(vis)); for(int i=1; i<=n; i++) { scanf("%s",ch[i]); for(int j=0; j<m; j++) { if(ch[i][j] == ‘X‘) Edge[i][j+1] = 0; } } getchar(); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(Edge[i][j] == 0) continue; Edge[i][j] = min(Edge[i-1][j],min(Edge[i+1][j],min(Edge[i][j-1],Edge[i][j+1]))) + 1; } } temp = 0; scanf("%d %d",&sx,&sy); scanf("%d %d",&ex,&ey); getchar(); int temp = bfs(); printf("%d\n",temp); } return 0; }
原文:http://www.cnblogs.com/chenyang920/p/4357934.html