题目大意：
输入n，（x，y）；n为阻挡的草堆数量，（x，y）为开始时拖拉机所在的位置
接下来n行每行一个坐标（a，b）；为各个草堆的坐标
输出拖拉机要回到原点（0,0）需要移动的草堆数量
Sample Input7 6 36 25 24 32 17 35 46 4
Sample Output1
HintINPUT DETAILS:
The tractor starts at (6,3). There are 7 bales of hay, at positions (6,2), (5,2), (4,3), (2,1), (7,3), (5,4), and (6,4).
OUTPUT DETAILS:
Farmer John only needs to remove one bale of hay to free his tractor.
直接从拖拉机的位置往外广搜整个矩阵 遇到边界就结束 遇到边界前的路径中最少草堆的一条有几个 优先队列升序排序可直接取出当前草堆数量最少的一条路 #include <iostream> #include <algorithm> #include <stdio.h> #include <stdlib.h> #include <cstring> #include <queue> #include <functional> using namespace std; struct NODE { int sp,x,y; NODE(){}; NODE(int spi,int xi,int yi): sp(spi),x(xi),y(yi){}; bool operator<(const NODE& p)const{ return sp>p.sp; /// 升序排序这里应该是 大于号！！ } }; int mov[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int G[1005][1005]; int st,ed,n; bool bound(int x,int y) { return x==0||y==0||x==1001||y==1001; } int main() { while(~scanf("%d",&n)) { scanf("%d%d",&st,&ed); memset(G,0,sizeof(G)); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); G[a][b]=1; } priority_queue < NODE > q; q.push(NODE(0,st,ed)); G[st][ed]=-1; while(!q.empty()) { NODE tmp=q.top(); q.pop(); if(bound(tmp.x,tmp.y)) { printf("%d\n",tmp.sp); break; }//printf("%d %d %d\n",tmp.x,tmp.y,tmp.sp); for(int i=0;i<4;i++) { int nowx=tmp.x+mov[i][0], nowy=tmp.y+mov[i][1], nowsp=tmp.sp; if(G[nowx][nowy]==-1) continue; if(G[nowx][nowy]) nowsp++; G[nowx][nowy]=-1; q.push(NODE(nowsp,nowx,nowy)); //printf("%d %d %d\n",nowx,nowy,nowsp); } } } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/8884136.html
