一,bfs
题1 1096. 地牢大师
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int h,n,m;
char g[N][N][N];
int dist[N][N][N];
struct Point{
int x,y,z;
}q[N*N*N];
Point S,T;
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
int bfs()
{
memset(dist,-1,sizeof dist);
dist[S.x][S.y][S.z]=0;
int hh=0,tt=0;
q[0]={S.x,S.y,S.z};
while(hh<=tt)
{
auto t=q[hh++];
for(int u=0;u<6;++u)
{
int x=t.x+dx[u],y=t.y+dy[u],z=t.z+dz[u];
if(x<0||x>=h||y<0||y>=n||z<0||z>=m) continue;
if(g[x][y][z]=='#'||~dist[x][y][z]) continue;
if(x==T.x&&y==T.y&&z==T.z) return dist[t.x][t.y][t.z]+1;
dist[x][y][z]=dist[t.x][t.y][t.z]+1;
q[++tt]={x,y,z};
}
}
return -1;
}
int main()
{
while(scanf("%d%d%d",&h,&n,&m),h||n||m)
{
for(int i=0;i<h;++i)
for(int j=0;j<n;++j)
scanf("%s",g[i][j]);
for(int i=0;i<h;++i)
for(int j=0;j<n;++j)
for(int k=0;k<m;++k)
{
if(g[i][j][k]=='S') S={i,j,k};
if(g[i][j][k]=='E') T={i,j,k};
}
int t=bfs();
if(~t) printf("Escaped in %d minute(s).\n",t);
else printf("Trapped!\n");
}
return 0;
}
题2 1233. 全球变暖
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=1010;
int n,res1,res2;
char g[N][N];
bool st[N][N];
vector<vector<PII>> path;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void bfs(int a,int b)
{
st[a][b]=true;
queue<PII> q;vector<PII> v;
q.push({a,b});v.push_back({a,b});
++res1;
bool flag=false;
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;++i)
{
int x=t.x+dx[i],y=t.y+dy[i];
if(x<0||x>=n||y<0||y>=n) continue;
if(g[x][y]=='.'||st[x][y]) continue;
st[x][y]=true;
q.push({x,y}),v.push_back({x,y});
}
}
path.push_back(v);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%s",g[i]);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(g[i][j]=='#'&&!st[i][j])
bfs(i,j);
for(int i=0;i<path.size();++i)
{
bool flag=false;
for(int j=0;j<path[i].size();++j)
{
int idx=0;
for(int k=0;k<4;++k)
{
int x=path[i][j].x+dx[k],y=path[i][j].y+dy[k];
if(x<0||x>=n||y<0||y>=n) continue;
if(st[x][y]) ++idx;
}
if(idx==4) flag=true;
}
if(flag) ++res2;
}
printf("%d",res1-res2);
return 0;
}
二,图论
题1 1224. 交换瓶子
#include<iostream>
using namespace std;
const int N=10010;
int n;
int b[N];
bool st[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
int cnt=0;
for(int i=1;i<=n;++i)
if(!st[i])
{
++cnt;
for(int j=i;!st[j];j=b[j])
st[j]=true;
}
printf("%d",n-cnt);
return 0;
}
题2 1207. 大臣的旅费
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=N*2;
int n;
int h[N],e[M],w[M],ne[M],idx;
int ans;
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u,int fa)
{
int d1=0,d2=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
int t=dfs(j,u)+w[i];
if(t>d1) d2=d1,d1=t;
else if(t>=d2) d2=t;
}
ans=max(ans,d1+d2);
return d1;
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d",&n);
for(int i=0;i<n-1;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
dfs(1,-1);
printf("%lld",ans*10+(ans+1ll)*ans/2);
return 0;
}