A - Breadth First Search
?
题意：
请编写一个程序，求给定的有向图G(V，E)?中顶点1到各顶点的最短路径( 路
径边数的最小值)。各顶点编号分别为1至n。如果从顶点1出发无法到达某顶点，则
与该顶点的距离记为- 1。
思路：
《挑战程序设计竞赛2 算法和数据结构》一书第232页BFS例题，模板题。
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
struct node
{
int x,pos;
node(){}
node(int xx,int pp):x(xx),pos(pp){}
};
int n,id,k,x;
bool a[105][105];
int b[105];
void bfs(){
queue<node> q;
int cnt=0;
q.push(node(1,0));
b[1]=0;
cnt++;
while(!q.empty()){
node tmp=q.front();
q.pop();
if(cnt==n) break;
for(int i=1;i<=n;i++){
if(b[i]!=-1) continue;
if(a[tmp.x][i]){
b[i]=tmp.pos+1;
q.push(node(i,b[i]));
}
}
}
}
int main(){
cin>>n;
memset(a,false,sizeof(a));
memset(b,-1,sizeof(b));
for(int i=0;i<n;i++){
cin>>id>>k;
for(int j=0;j<k;j++){
cin>>x;
a[id][x]=true;
}
}
bfs();
for(int i=1;i<=n;i++){
cout<<i<<" "<<b[i]<<endl;
}
}
B - Depth First Search
题意：
在图的搜索算法中，深度优先搜索采取的思路是尽可能地访问相邻顶点。设仍存
在未搜索邻接边的顶点中最后一个被发现的顶点为V，那么深度优先搜索就是对顶点V的邻接边递归地进行搜索, 当v 的边全部搜索完毕后，程序沿发现v 时所经过的边回归，继续搜索前一顶点。
搜索一直持续到发现当前起点可到达的所有顶点为止。如果仍有顶点未被发现，则选择其中编号最小的一个作为新起点继续搜索。
深度优先搜索中，需要对各顶点记录以下两个时间戳，
? 时间戳d[v]: 记录第一次访问v 的时刻（ 发现时刻）
? 时间戳f[v]: 记录调查完v 的邻接表的时刻（ 结束时刻）
请基于以下需求编写一个程序， 对给定的有向图G = (V，E) 进行深度优先搜索，并显示其执行过程。
? G 以邻接表的形式给出。各顶点编号为1至n
? 各邻接表的顶点编号按升序排列
? 程序报告各顶点的发现时刻和结朿时刻
? 深度优先搜索过程中，如果同时出现多个待访问的顶点， 则选择其中最小的一个进行访问
? 首个被访问顶点的开始时刻为1
思路：
《挑战程序设计竞赛2 算法和数据结构》一书第224页DFS例题，模板题。
-
考察点：搜索，DFS
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
int n,id,k,x,t;
bool a[105][105];
int bt[105];
int et[105];
bool vis[105];
void dfs(int id){
++t;
bt[id]=t;
vis[id]=true;
for(int i=1;i<=n;i++){
if(a[id][i]&&!vis[i])
dfs(i);
}
t++;
et[id]=t;
}
int main(){
cin>>n;
memset(a,false,sizeof(a));
memset(vis,false,sizeof(vis));
memset(bt,-1,sizeof(bt));
memset(et,-1,sizeof(et));
for(int i=0;i<n;i++){
cin>>id>>k;
for(int j=0;j<k;j++){
cin>>x;
a[id][x]=true;
}
}
t=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
}
}
for(int i=1;i<=n;i++){
cout<<i<<" "<<bt[i]<<" "<<et[i]<<endl;
}
}
C - 非常可乐
思路：
1.BFS：?点我查看题解
2.数论：大佬题解
-
考察点：搜索，BFS，数论
D - Amazing Mazes
题意：
现在有一个h*w的迷宫，迷宫的外围被墙所包围，入口与出口处没有墙。
接下来的2*h-1行，奇数行代表相邻空格之间是否有墙，1为有墙，0没有；
偶数行代表上下空格之间有无墙体，1为有墙，0没有；
问最少需要多少时间走出迷宫？
如果走不出来，输出0。
思路：
很简单的一道题，难点在于如何重建迷宫。
我们把墙体也算入迷宫之内，那么重建的迷宫方阵大小为（2*w+1）*（2*h+1）。
第一行、最后一行、第一列、最后一列按照题目要求围上墙。
?我们定义：
mp[i][j]==1 (i,j)处有墙
mp[i][j]==0 (i,j)处没有墙?奇数行代表墙，偶数行代表房间。奇数列代表墙，偶数列代表房间。
由此可以得出每次行动都是移动2格，但是移动时需要考虑中间是否有墙。
具体看代码。
-
考察点：DFS，搜索
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int x,y;
int step;
node(){}
node(int xx,int yy,int ss):x(xx),y(yy),step(ss){}
};
int mp[100][100];
bool vis[100][100];
int ex,ey,h,w;
int dx[4]={2,-2,0,0};
int dy[4]={0,0,2,-2};
void make_map()
{
memset(mp,0,sizeof(mp));
for(int i=0;i<=2*h;i++){
if(i==0||i==2*h) //上下的墙
{
for(int j=0;j<=2*w;j++)
mp[i][j]=1;
}
else
mp[i][0]=mp[i][2*w]=1;//左右的墙
}
for(int i=1;i<2*h;i++){
if(i%2){
for(int j=0;j<w-1;j++)
cin>>mp[i][2*j+2];
}
else{
for(int j=0;j<w;j++)
cin>>mp[i][2*j+1];
}
}
ex=2*h-1;
ey=2*w-1;
}
int bfs()
{
queue<node> q;
q.push(node(1,1,0));
vis[1][1]=true;
while(!q.empty()){
node tmp=q.front();
q.pop();
if(tmp.x==ex&&tmp.y==ey)
return tmp.step;
for(int i=0;i<4;i++){
int xx=tmp.x+dx[i];
int yy=tmp.y+dy[i];
if(xx>=2*h||xx<=0||yy>=2*w||yy<=0) continue;
if(mp[(xx+tmp.x)/2][(yy+tmp.y)/2]==1) continue;
if(mp[xx][yy]==1) continue;
if(vis[xx][yy]) continue;
vis[xx][yy]=true;
q.push(node(xx,yy,tmp.step+1));
}
}
return -1;
}
int main()
{
while(cin>>w>>h&&w&&h)
{
make_map();
memset(vis,false,sizeof(vis));
int ans=bfs();
if(ans==-1) cout<<"0\n";
else cout<<ans+1<<"\n";
}
}
E - A计划
题意：
中文题你问我题意？
思路：
多层的迷宫和一层迷宫差不多，只不过多了一个z轴上的移动。
但是我们要搞清楚这道题中上下层互换并不是我们主动形成的。
也就是说，你如果想去另一层，你不能自发地前往，你只能通过题目中提及到的“时空传输机”被动式的被传送到另一层。
注意到这一点之后再去考虑如何表示两层之间的互换，博主这里利用的是异或的性质：
1^1==0
0^1==1?剩下的就是细节上的处理。
-
考察点：搜索，BFS，异或
-
坑点：当遇到‘#’（时空传输机）的时候如何处理
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
struct node
{
int x,y,h,step;
node() {}
node(int hh,int xx,int yy,int ss):x(xx),y(yy),h(hh),step(ss) {}
};
int n,m,t;
string mp[5][20];
bool vis[5][20][20];
int dx[4]= {1,-1,0,0};
int dy[4]= {0,0,1,-1};
int bfs()
{
queue<node> q;
memset(vis,false,sizeof(vis));
q.push(node(0,0,0,0));
vis[0][0][0]=true;
while(!q.empty())
{
node tmp=q.front();
q.pop();
for(int i=0; i<4; i++)
{
int xx=tmp.x+dx[i];
int yy=tmp.y+dy[i];
int hh=tmp.h;
if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[hh][xx][yy]&&mp[hh][xx][yy]!='*') //不超界，没走过，不是障碍物
{
vis[hh][xx][yy]=true;
if(mp[hh][xx][yy]=='.')
{
q.push(node(hh,xx,yy,tmp.step+1));
}
else if(mp[hh][xx][yy]=='#'){
if(mp[hh^1][xx][yy]=='.'&&!vis[hh^1][xx][yy]){
vis[hh^1][xx][yy]=true;
q.push(node(hh^1,xx,yy,tmp.step+1));
}
else if(mp[hh^1][xx][yy]=='P')
return tmp.step+1;
}
else if(mp[hh][xx][yy]=='P')
return tmp.step+1;
}
}
}
return -1;
}
int main()
{
// cout<< (1^1) <<endl;
// cout<< (0^1) <<endl;
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int c;
cin>>c;
while(c--)
{
cin>>n>>m>>t;
for(int i=0; i<n; i++)
cin>>mp[0][i];
for(int i=0; i<n; i++)
cin>>mp[1][i];
int time=bfs();
if(time==-1||time>t)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
return 0;
}
F - Oil Deposits
题意：
假设在（x ,y）处有一块油田，如果在（x+1 ,y）、（x ,y+1）、（x-1 ,y）、（x ,y-1）、（x+1 ,y+1）、（x+1 ,y-1）、（x-1 ,y+1）、（x-1 ,y-1）处也有一块油田，我们认为这其实是一块油田。
现给出油田的分布图，请给出图中共有多少块不同的油田？
思路：
深搜，为每一个已被遍历过的油田做上标记，如果当前油田未被标记，则证明这是一块新油田，对它进行深搜，将它的同源共生油田标记上。
-
考察点：搜索，DFS
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
string mp[105];
int vis[105][105];
int ans;
int n,m;
int dx[8]= {0,0,1,-1,1,-1,-1,1};
int dy[8]= {1,-1,1,-1,0,0,1,-1};
void dfs(int x,int y,int id){
vis[x][y]=id;
for(int i=0;i<8;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx>=n||xx<0||yy>=m||yy<0) continue;
if(!vis[xx][yy]&&mp[xx][yy]=='@'){
vis[xx][yy]=id;
dfs(xx,yy,id);
}
}
}
int main()
{
while(cin>>n>>m&&m){
for(int i=0;i<n;i++)
cin>>mp[i];
memset(vis,0,sizeof(vis));
ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(!vis[i][j]&&mp[i][j]=='@')
{
ans++;
dfs(i,j,ans);
}
}
cout<<ans<<endl;
}
return 0;
}
G - DNA sequence
题意：
给出n个长度不超过8的字符串，请你给出一个字符串s，满足：
这n个字符串都是s的子序列。
如果有多个s满足，请输出最短的那个。
思路：
深搜+IDA*(迭代加深)。
我们在每次DFS时控制当前的递归深度，若递归达到指定深度后仍无法达成目标，则结束递归。
根据题目可知：
- s的最短长度为n个字符串中最长的字符串的长度len。
我们从len开始递归，每次限制当前DFS所得出的s长度。
设置match数组：
match[i]==x 对于当前的字符串s而言，第i个字符串中已经有x个字符匹配上了递归结束条件：
- 已出现答案
- 当前长度大于规定长度
- 当前长度+最多未匹配的字符串的未匹配字符数量>规定长度
具体见代码。
-
考察点：搜索，DFS，剪枝，IDA*
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
char words[8]="AGCT";
bool vis[8][8];
char mp[8][8];
int t,n,m,ans,len;
void dfs(int n_len,int match[])
{
if(ans)
return;
if(n_len>len)
return ;
int no_match=0;
for(int i=0; i<n; i++)
no_match=max((int)(strlen(mp[i]))-match[i],no_match);
if(no_match==0) //没有不匹配的字符
{
ans=n_len;
return;
}
if(no_match+n_len>len)
return;
for(int i=0; i<4; i++)
{
bool flag=false;
int n_match[8];
for(int j=0; j<n; j++)
{
if(mp[j][match[j]]==words[i])
{
flag=true;
n_match[j]=match[j]+1;
}
else
n_match[j]=match[j];
}
if(flag)
dfs(n_len+1,n_match);
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
len=-1;
scanf("%d",&n);
int match[8]; //第i个字符串已经匹配的字符个数 / 第i个字符该对哪个字符进行匹配
for(int i=0; i<n; i++)
{
scanf("%s",mp[i]);
len=max((int)(strlen(mp[i])),len);
match[i]=0;
//printf("%s\n",mp[i]);
}
ans=0;
while(!ans)
{
dfs(0,match);
len++;
}
printf("%d\n",ans);
}
}