1、细胞
（1）题目描述
一矩形阵列由数字0 到9 组成,数字1 到9 代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:
阵列
4 10 0234500067 1034560500 2045600671 0000000089 有4 个细胞。
【输入】 第一行为矩阵的行n 和列m ;
下面为一个n×m 的矩阵。
【输出】 细胞个数。
【输入样例】 4 10 0234500067 1034560500 2045600671 0000000089 【输出样例】 4
（2）AC代码
BFS
#include <iostream>
#include <cstring>
#include<map>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char mat[105][105];
int vis[105][105];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node
{
int x,y;
};
void bfs(int x,int y)
{
vis[x][y]=true;
node pos;
pos.x=x,pos.y=y;
queue<node> q;
q.push(pos);
while(!q.empty())
{
node cur = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=cur.x+dir[i][0];
int yy=cur.y+dir[i][1];
if(!vis[xx][yy] && mat[xx][yy] != '0' && xx>=0 && xx<n && yy>=0 && yy<m)
{
node next;
next.x=xx;
next.y=yy;
q.push(next);
vis[xx][yy]=true;
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mat[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!vis[i][j] && mat[i][j] != '0')
{
bfs(i,j);
ans++;
}
}
}
cout<<ans;
return 0;
}DFS
#include <iostream>
#include <cstring>
#include<map>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char mat[105][105];
int vis[105][105];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
vis[x][y]=true;
for(int i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(!vis[xx][yy] && mat[xx][yy] != '0' && xx>=0 && xx<n && yy>=0 && yy<m)
dfs(xx,yy);
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mat[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!vis[i][j] && mat[i][j] != '0')
{
dfs(i,j);
ans++;
}
}
}
cout<<ans;
return 0;
}2、最少步数
（1）题目描述
在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。
【输入】 A、B两点的坐标。
【输出】 最少步数。
【输入样例】 12 16 18 10 【输出样例】 8 9
（2）AC代码
#include <iostream>
#include <cstring>
#include<map>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int vis[105][105];// 记录点是否在队列中
int dir[12][2]={{2,1},{-2,-1},{2,-1},{-2,1},{1,2},{-1,-2},{-1,2},{1,-2},{2,2},{-2,-2},{-2,2},{2,-2}};
struct node
{
int x,y,step;// step是起点到点(x,y)的最短步数
};
int bfs(node s,node t)
{
fill(vis[0],vis[0]+105*105,false);
queue<node> q;
q.push(s);
vis[s.x][s.y]=true;
while(!q.empty())
{
node cur =q.front();
q.pop();
if(cur.x==t.x && cur.y==t.y)
return cur.step;
for(int i=0;i<12;i++)
{
int xx = cur.x+dir[i][0];
int yy = cur.y+dir[i][1];
if(!vis[xx][yy] && xx>=1 && xx<=100 && yy>=0 && yy<=100)
{
node next;
next.x=xx,next.y =yy,next.step=cur.step+1;
q.push(next);
vis[xx][yy]=true;
}
}
}
}
int main()
{
node s,a,b;
s.x=1,s.y=1,s.step=0; // 初始化起点
cin>>a.x>>a.y>>b.x>>b.y;
int ans1=bfs(s,a);
int ans2=bfs(s,b);
cout<<ans1<<endl<<ans2;
return 0;
}3、Dungeon Master
（1）题目描述
这题是一个三维的迷宫题目，其中用‘.’表示空地，‘#’表示障碍物，‘S’表示起点，‘E’表示终点，求从起点到终点的最小移动次数，解法和二维的类似，只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动，每次都只能移到相邻的空位，每次需要花费一分钟，求从起点到终点最少要多久。
【输入】 多组测试数据。
一组测试测试数据表示一个三维迷宫：
前三个数，分别表示层数、一个面的长和宽，后面是每层的平面图。前三个数据为三个零表示结束。
【输出】 最小移动次数。
【输入样例】 3 4 5 S.... .###. .##.. ###.#
##.## ##...
#.### ####E 1 3 3 S## #E#
0 0 0 【输出样例】 Escaped in 11 minute(s). Trapped!
（2）AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=31;
int l,r,c;// 迷宫的层数，每层的行数、列数
char mat[N][N][N];
bool vis[N][N][N];
int dir[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
struct node
{
int x,y,z,step;
};
int bfs(node s,node t)
{
memset(vis,false,sizeof(vis));
queue<node> q;
q.push(s);
vis[s.x][s.y][s.z] = true;
while(!q.empty())
{
node cur = q.front();
q.pop();
if(cur.x==t.x && cur.y == t.y && cur.z == t.z)
return cur.step;
for(int i=0;i<6;i++)
{
int xx = cur.x+dir[i][0];
int yy = cur.y+dir[i][1];
int zz = cur.z+dir[i][2];
if(vis[xx][yy][zz] || mat[xx][yy][zz] == '#')continue;
if(xx<0 || xx>=l || yy<0 || yy>=r || zz <0 || zz>=c)continue;
node next;
next.x=xx,next.y=yy,next.z=zz,next.step=cur.step+1;
q.push(next);
vis[xx][yy][zz]=true;
}
}
return -1;
}
int main()
{
while(cin>>l>>r>>c)
{
node S,E;
if(l==0 && r==0 && c==0)break;
for(int i=0;i<l;i++)
{
for(int j=0;j<r;j++)
{
for(int k=0;k<c;k++)
{
cin>>mat[i][j][k];
if(mat[i][j][k] == 'S')
{
S.x=i,S.y=j,S.z=k,S.step=0;
mat[i][j][k] = '.';
}else if(mat[i][j][k] == 'E')
{
E.x=i,E.y=j,E.z=k;
mat[i][j][k] = '.';
}
}
}
}
int res=bfs(S,E);
if(res<0)
{
cout<<"Trapped!"<<endl;
}else
{
cout<<"Escaped in "<<res<<" minute(s)."<<endl;
}
}
return 0;
}4、Knight Moves
（1）题目描述
输入n 代表有个n×n 的棋盘，输入开始位置的坐标和结束位置的坐标，问一个骑士朝棋盘的八个方向走马字步，从开始坐标到结束坐标可以经过多少步。
【输入】 首先输入一个n ,表示测试样例的个数。
每个测试样例有三行。
第一行是棋盘的大小L(4≤L≤300) ；
第二行和第三行分别表示马的起始位置和目标位置(0..L−1) 。
【输出】 马移动的最小步数，起始位置和目标位置相同时输出0 。
【输入样例】 3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1 【输出样例】 5 28 0
（2）
#include<bits/stdc++.h>
using namespace std;
const int N=301;
int n,l;// 测试数据个数，棋盘大小
bool vis[N][N];
int dir[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
struct node
{
int x,y,step;
};
int bfs(node s,node t)
{
memset(vis,false,sizeof(vis));
queue<node> q;
q.push(s);
vis[s.x][s.y] = true;
while(!q.empty())
{
node cur = q.front();
q.pop();
if(cur.x==t.x && cur.y == t.y)
return cur.step;
for(int i=0;i<8;i++)
{
int xx = cur.x+dir[i][0];
int yy = cur.y+dir[i][1];
if(vis[xx][yy])continue;
if(xx<0 || xx>=l || yy<0 || yy>=l)continue;
node next;
next.x=xx,next.y=yy,next.step=cur.step+1;
q.push(next);
vis[xx][yy]=true;
}
}
return -1;
}
int main()
{
cin>>n;
while(n)
{
n--;
cin>>l;
node S,E;
cin>>S.x>>S.y>>E.x>>E.y;
S.step=0;
int res=bfs(S,E);
cout<<res<<endl;
}
return 0;
}5、献给阿尔吉侬的花束
（1）题目描述
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
【输入】 第一行是一个正整数T（1 ≤ T ≤ 10），表示一共有T组数据。
每一组数据的第一行包含了两个用空格分开的正整数R和C（2 ≤ R, C ≤ 200），表示地图是一个R×C的矩阵。
接下来的R行描述了地图的具体内容，每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。
【输出】 对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。
【输入样例】 3 3 4 .S.. ###. ..E. 3 4 .S.. .E.. .... 3 4 .S..
..E. 【输出样例】 5 1 oop!
（2）
#include<bits/stdc++.h>
using namespace std;
const int N=201;
int n,r,c; // 测试数据组数、行数、列数
char mat[N][N];
bool vis[N][N];
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
struct node
{
int x,y,time;
};
int bfs(node s,node t)
{
memset(vis,false,sizeof(vis));
queue<node> q;
q.push(s);
vis[s.x][s.y]=true;
while(!q.empty())
{
node cur = q.front();
q.pop();
if(cur.x==t.x && cur.y == t.y)
return cur.time;
for(int i=0;i<4;i++)
{
node next;
next.x=cur.x+dir[i][0],next.y=cur.y+dir[i][1];
next.time=cur.time+1;
if(next.x <0 || next.x >=r || next.y <0 || next.y >=c)continue;
if(vis[next.x][next.y] || mat[next.x][next.y] == '#')continue;
q.push(next);
vis[next.x][next.y]=true;
}
}
return -1;
}
int main()
{
cin>>n;
while(n)
{
node S,E;
n--;
cin>>r>>c;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
cin>>mat[i][j];
if(mat[i][j]=='S')
{
S.x=i,S.y=j,S.time=0;
mat[i][j]='.';
}else if(mat[i][j]=='E')
{
E.x=i,E.y=j;
mat[i][j]='.';
}
}
}
int res=bfs(S,E);
if(res<0)
{
cout<<"oop!"<<endl;
}else{
cout<<res<<endl;
}
}
return 0;
}6、抓住那头牛
（1）题目描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000) ，牛位于点K(0≤K≤100000) 。农夫有两种移动方式：
1、从X 移动到X−1 或X+1 ，每次移动花费一分钟
2、从X移动到2×X ，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
【输入】 两个整数，N 和K 。
【输出】 一个整数，农夫抓到牛所要花费的最小分钟数。
【输入样例】 5 17 【输出样例】 4
（2）
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,k;
int dir[3];
int t[N];
void bfs()
{
memset(t,-1,sizeof(t)); // 初始化农夫到各点的的时间，且作为标记数组，
//为-1表示未访问过该点，其他数字表示到该点的时间
queue<int> q;
q.push(n);
t[n]=0; // 农夫到自己位置的时间为0
while(!q.empty())
{
int cur = q.front();
q.pop();
if(cur==k)return; // 找到牛的位置
// 三种可走的方式
dir[0]=cur-1;
dir[1]=cur+1;
dir[2]=cur*2;
for(int i=0;i<3;i++)
{
if(dir[i]>=0 && dir[i]<=100000 && t[dir[i]] == -1)
{
q.push(dir[i]);
t[dir[i]]=t[cur]+1;
}
}
}
}
int main()
{
cin>>n>>k;
bfs();
cout<<t[k]<<endl;
return 0;
}