目录

1.Acwing 武士风度的牛  188（跟迷宫类似）

2.全球变暖（2018省赛）

3.跳蚱蜢  （2017年省赛）

1.Acwing 武士风度的牛  188（跟迷宫类似）

1.先建图

2.找出起点和终点

3.开始dfs()

4.用优先队列，把起点装入队列

a.弹出队列中的第一个，走下一步bfs，先判断是不是终点

b.判断出界，continue；判断标记；continue；判断障碍；continue

c.步数+1

d.打入队列，打标记

import sysfrom queue import *n,m=map(int,input().split())b=[]for i in range(m):     a=list(input())     b.append(a)for i in range(m):     for j in range(n):   if b[i][j]=='K': x,y=i,j   if b[i][j]=='H': e,d=i,jvis=[[0 for i in range(n)]for j in range(m)]dir=[[2,1],[-2,1],[2,-1],[-2,-1],[-1,2],[1,2],[-1,-2],[1,-2]]q=Queue()def bfs():     q.put((x,y,0))     vis[x][y]=1     while not q.empty():   now=q.get()   if now[0]==e and now[1]==d: print(now[2]) sys.exit()   for i in range(8): next_x=now[0]+dir[i][0] next_y=now[1]+dir[i][1] if next_x<0 or next_y=m or next_y>=n:      continue if vis[next_x][next_y]==1:      continue if b[next_x][next_y]=='*':      continue next_path=now[2]+1 q.put((next_x,next_y,next_path)) vis[next_x][next_y]=1print(bfs())

2.全球变暖（2018省赛）

题目描述

你有一张某海域 NxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：

.......

.##....

.##....

....##.

..####.

...###.

.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......

.......

.......

.......

....#..

.......

.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入描述

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出描述

输出一个整数表示答案。

样例输入

7........##.....##........##...####....###........

样例输出

1 

1.用bfs

先找到一块陆地，然后判断他是不是高地，如果不是，在判断周围的陆地是不是高地，判断完要打上标记，如果是，就把flag改为1，继续把周围的陆地打上标记

2.最后遍历，条件是打过标记和是陆地的，加上所有flag为0的

from queue import *vis=[[0 for i in range(1005)]for j in range(1005)]n=int(input())b=[]for i in range(n):    b.append(list(input()))def dfs(x,y):    dir=[(0,1),(0,-1),(1,0),(-1,0)]    q=Queue()    q.put((x,y))    flag=0    while not q.empty(): now=q.get() now_x=now[0] now_y=now[1] if flag==0:     if b[now_x+1][now_y]=='#' and b[now_x-1][now_y]=="#" and b[now_x][now_y+1]=="#" and b[now_x][now_y-1]=="#":  flag=1 for i in range(4):     next_x=now_x+dir[i][0]     next_y=now_y+dir[i][1]     if vis[next_x][next_y]==0 and b[next_x][next_y]=="#":  q.put((next_x,next_y))  vis[next_x][next_y]=1    if flag==1: return False    if flag==0: return Trueans=0for i in range(n):    for j in range(n): if b[i][j]=='#' and vis[i][j]==0:     if dfs(i,j):  ans+=1print(ans)

3.跳蚱蜢  2017年省赛

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如下图所示： 有 9 只盘子，排成 1 个圆圈。 其中 8 只盘子内装着 8 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1 ~ 8。

每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1-8换位，2−7换位,...），至少要经过多少次跳跃？ 

1.用bfs,先确定起始形态和终止形态，

2.先把起始形态放入队列中，然后取出第一个，让他顺时针走一个，两个；逆时针走一个，两个；

然后记住步数，别忘了最后要把交换的位置返回

3.把放入过队列的，打上标记，重复上述操作

4. 找到终点最后输出步数

from math import *from queue import *mp={}a1='012345678'a2='087654321'q=Queue()q.put((a1,0))mp[a1]=1while not q.empty():  now=q.get()  x=now[0]  if x==a2:    print(now[1])    break  t=list(x)  j=t.index('0')  for i in range(-2,3):    i0=divmod(i+j+9,9)[1]    t[j],t[i0]=t[i0],t[j]    y="".join(t)    if y not in mp:      mp[y]=1      w=now[1]+1      q.put((y,w))    t[j],t[i0]=t[i0],t[j]   

局座张召忠