PID195 / 校园迷宫☆
从x,y走到去q,w的最小步数，限制是有的点可走，有的点不可走，BFS嘛。
#include<bits/stdc++.h> using namespace std; int n,m,a[2005][2005],b[2005][2005],q,w,e,r,ans; int dx[]={0,0,1,-1}, dy[]={1,-1,0,0}; queue<pair<int,int> >Q; bool vis[2005][2005]; void bfs(){ vis[q][w]=1; Q.push(make_pair(q,w)); while(!Q.empty()){ int x=Q.front().first,y=Q.front().second;Q.pop(); if(x==e&&y==r){ ans=b[x][y]; break; } for(int i=0;i<4;i++) { int tx=x+dx[i],ty=y+dy[i]; if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&!vis[tx][ty]&&!a[tx][ty]){ b[tx][ty]=b[x][y]+1; vis[tx][ty]=1; Q.push(make_pair(tx,ty)); } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } scanf("%d%d%d%d",&q,&w,&e,&r); bfs(); if(!ans) printf("No Answer! "); else printf("%d ",ans); return 0; }
PID335 / 流星雨☆
Bessie听说有一场壮丽的流星雨即将来临，而且据说陨石将要落下来撞击地球并摧毁一切它遇到的东西。为了保证自己的安全，bessie决定到一个安全的（永远不会被陨石击毁）地方去。
报道表明将有M颗陨石落下（1 ≤ M ≤ 50,000)，第i个陨石将在Ti(0 ≤ Ti ≤ 1,000)时刻砸中（Xi,Yi)点(0 ≤ Xi ≤ 300； 0 ≤ Yi ≤ 300) 。每颗陨石将击毁它直接砸中的点以及四个与其直接相邻的点
她现在所处的地方是坐标系的原点，并从零时刻起出发，前往一个安全的地点，要求是她经过某点时该点未被击毁。她只能在坐标系的第一象限以及x，y轴的正半轴上活动。
求她能到达一个安全地点的最短时间。
BFS嘛，跟上一题差不多
#include<bits/stdc++.h> using namespace std; int a[505][505],m; int b[2005][2005],ans=-1; int dx[]={0,0,1,-1}, dy[]={1,-1,0,0}; queue<pair<int,int> >Q; bool vis[2005][2005]; void bfs(){ vis[0][0]=1; Q.push(make_pair(0,0)); while(!Q.empty()){ int x=Q.front().first,y=Q.front().second;Q.pop(); // if(x==0&&y==0) goto end; if(a[x][y]>1000){ ans=b[x][y]; break; } // end: for(int i=0;i<4;i++) { int tx=x+dx[i],ty=y+dy[i]; if(tx>=0&&ty>=0&&tx<=400&&ty<=400&&!vis[tx][ty]&&a[tx][ty]>b[x][y]+1){ b[tx][ty]=b[x][y]+1; vis[tx][ty]=1; Q.push(make_pair(tx,ty)); } } } } int main() { scanf("%d",&m); memset(a,0x3f,sizeof(a)); for(int t,x,y,i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&t); a[x][y]=min(t,a[x][y]); for(int k=0;k<4;k++){ if(x+dx[k]>=0&&y+dy[k]>=0) a[x+dx[k]][y+dy[k]]=min(a[x+dx[k]][y+dy[k]],t); } } bfs(); printf("%d ",ans); return 0; }
2999: 卫星照片 USACO 2005 NOV
求出最大的联通块大小
#include<bits/stdc++.h> using namespace std; int n,m; char a[1005][1005]; int ans; int dx[]={0,0,1,-1}, dy[]={1,-1,0,0}; bool vis[2005][2005]; queue<pair<int,int> >Q; int bfs(int x,int y){ int an=0; Q.push(make_pair(x,y)); vis[x][y]=1; while(!Q.empty()){ int x=Q.front().first,y=Q.front().second;Q.pop();++an; for(int i=0;i<4;i++){ int tx=x+dx[i],ty=y+dy[i]; if(!vis[tx][ty]&&a[tx][ty]=='*'&&tx>=1&&ty>=1&&tx<=n&&ty<=m){ vis[tx][ty]=1; Q.push(make_pair(tx,ty)); } } } return an; } int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(!vis[i][j]&&a[i][j]=='*'){ ans=max(bfs(i,j),ans); } } } printf("%d ",ans); return 0; }