#赵美延MCountdownMC# [女孩儿]#赵美延实力主唱#
【TWI】210426更新美延相关

传闻的孩子们 这周带你 赏栗花! 面st(Gidle 美延)和 Weeekly(李受珍 Monday)以及 PURPLE KISS(罗高恩 Swan)将会一起去找宝藏 做live和游玩✨ 短信号码 7117 带上[传闻的孩子们]的标语 发送有春天气息的歌曲的话 可能会唱给你听..?(短信费用100元) #NOWOnAir

/kr_now

https://t.cn/A6PgUR3O
https://t.cn/Ai0siSYT
https://t.cn/Ai0sMI1y

❤【装饰透卡/自拍小卡/生日特典】国内邮费补邮 https://t.cn/A6cCNeYT
招新公告https://t.cn/AiNMRVRG
新粉必看 https://t.cn/Ec8Cm1Z ​​​

常规BFS
#include
using namespace std;

bool vis[9][9];
struct Node{
int x,y;
int path;
};
int dir[8][2]={2,1,2,-1,-2,-1,-2,1,1,2,1,-2,-1,-2,-1,2};
char s[4],e[4];
int sx,xy,ex,ey;

bool check(int x,int y){
if(x<=0||x>8||y<=0||y>8||vis[x][y])
return false;
else
return true;
}
int bfs(int sx,int sy,int ex,int ey){
memset(vis,0,sizeof(vis));
queue q;
q.push({sx,sy,0});
vis[sx][sy]=1;
while(q.size()){
Node now=q.front();
q.pop();
if(now.x==ex&&now.y==ey){//已经到达终点

return now.path;
}
for(int i=0;i<8;i++){

int xx=now.x+dir[i][0];

int yy=now.y+dir[i][1];

if(check(xx,yy)){

q.push({xx,yy,now.path+1});

vis[xx][yy]=1;

}
}
}
}

int main(int argc, char** argv) {

while(scanf("%s\0",s)!=EOF){
scanf("%s",e);
int sx=s[0]-'a'+1,sy=s[1]-'0';
int ex=e[0]-'a'+1,ey=e[1]-'0';

int path=bfs(sx,sy,ex,ey);

printf("To get from %s to %s takes %d knight moves.\n",s,e,path);
}
return 0;
}

求图的连通分量个数，统计bfs调用次数。
#include
using namespace std;

const int N=100+3;
char maze[N][N];
bool vis[N][N];
int n=0,m=0;
int dir[8][2]={{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}};
struct Node{
int x,y;
};

bool check(int x,int y){
if(maze[x][y]=='@'&&x>=0&&x=0&&y return true;
else
return false;
}
void bfs(int x,int y){
queue q;
q.push({x,y});
vis[x][y]=1;
while(q.size()){
Node now=q.front();
q.pop();
int xx,yy;
for(int i=0;i<8;i++){

xx=now.x+dir[i][0];

yy=now.y+dir[i][1];

if(check(xx,yy)){

q.push({xx,yy});

vis[xx][yy]=1;

}
}

}
}

int main(int argc, char** argv) {
while(scanf("%d %d\n",&n,&m)!=EOF){
if(m==0&&n==0)

break;
for(int i=0;i

string str;

cin>>str;

strcpy(maze[i],str.c_str());
}
int num=0;
memset(vis,0,sizeof(vis));
for(int i=0;i

for(int j=0;j

if(maze[i][j]=='@'&&!vis[i][j]){

bfs(i,j);

num++;

}

}
}
printf("%d\n",num);
}

return 0;
}