1. 营救
铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。
通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。
为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。
【输入格式】
第一行为n（0<n<=100）,下面是一个n*n的0、1矩阵，表示海洋地图；最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。
【输出格式】
哥伦比亚号到铁塔尼号的最短距离。
【样例输入】
3
0 0 1
1 0 1
1 0 0
1 1 3 3
【样例输出】
4
#include <iostream> using namespace std;
struct node{
int x;
int y;
int step;
};
struct node que[];
int map[][];
int book[][];
//int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int n,sx,sy,ex,ey,tx,ty,flag = ;
int head = ,tail = ;
void bfs(){
int next[][] = {{,},{,},{,-},{-,}};
que[tail].x = sx;
que[tail].y = sy;
que[tail].step = ;
tail++;
book[sx][sy] = ;
while(head < tail){
for(int i = ;i < ;i++){
tx = que[head].x + next[i][];
ty = que[head].y + next[i][];
if(tx < || tx > n || ty < || ty > n){
continue;
}
if(map[tx][ty] == && book[tx][ty] == ){
book[tx][ty] = ;
que[tail].x = tx;
que[tail].y = ty;
que[tail].step = que[head].step + ;
tail++;
}
if(tx == ex && ty == ey){
flag = ;
break;
}
}
if(flag == ){
break;
}
head++;
}
}
int main(){
cin >> n;
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
cin >> map[i][j];
}
}
cin >> sx >> sy >> ex >> ey;
bfs();
cout << que[tail-].step << endl;
return ;
}
2、抓住那头牛
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始于点N（0<=N<=100000），牛位于点K（0<=K<=100000）。农夫有两种移动方式：
1、从X移动到X-1或者X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花费多少时间才能抓住牛？
【输入格式】
两个整数，N和K
【输出样例】
一个整数，农夫抓到牛所要花费的最小分钟数
【样例输入】
5 17
【样例输出】
4
#include <iostream> using namespace std;
int n,k,x;
bool v[];
int h[][];
int main(){
cin >> n >> k;
h[][] = n,v[n] = ;
int head = ,tail = ;
do{
head++;
for(int i = ;i <= ;i++){
x = h[head][];
if(i == )
x++;
if(i == )
x--;
if(i == )
x *= ;
if(x >= && x <= )
if(!v[x] || h[x][] > h[h[head][]][]+ ){
tail++;
h[tail][] = x;
v[x] = ;
h[x][] = h[h[head][]][]+;
}
}
}while(head < tail);
cout << h[k][] << endl;
return ;
}
1、Knight Moves
输入L，代表有L*L的棋盘，输入开始位置的坐标和结束位置的坐标，问一个骑士朝棋盘的八个方向走马字步，从开始坐标到结束坐标可以经过多少步。
【输入格式】
首先输入一个n(0<n<=50)，表示测试样例的个数。每个测试样例有三行。第一行是棋盘的大小L(4<=L<=100)。第二行和第三行分别表示马的起始位置和目标位置(0~L-1)。
【输出格式】
马移动的最小步数，起始位置和目标位置相同时输出0。
【样例输入】
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
【样例输出】
5
28
0
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring> using namespace std;
int fx[] = {,,,,-,-,-,-};
int fy[] = {,-,,-,,-,,-};
int N,n,sx,sy,ex,ey,h[][];
int res[];
bool visited[][];
int work(int sx,int sy,int ex,int ey){
if((sx == ex) && (sy == ey))
return ;
memset(visited,,sizeof(visited));
// for(int i = 0;i < 1000;i++){
// for(int j = 0;j < 1000;j++){
// visited[i][j] = 0;
// }
// }
int t = ,w = ;
h[][] = sx,h[][] = sy,h[][] = ;
do{
t++;
int x = h[t][],y = h[t][];
for(int i = ;i < ;i++){
int X = x + fx[i],Y = y + fy[i];
if(X >= && X < n && Y >= && Y < n && !visited[X][Y]){
w++;
h[w][] = X;
h[w][] = Y;
h[w][] = h[t][] + ;
visited[X][Y] = ;
if(X == ex && Y == ey)
return h[w][];
}
}
}while(t < w);
}
int main(){
cin >> N;
for(int i = ;i <= N;i++){
cin >> n >> sx >> sy >> ex >> ey;
res[i] = work(sx,sy,ex,ey);
}
for(int j = ;j <= N;j++){
cout <<res[j] << endl;
}
return ;
}
2. Lake Counting
有一块N*M（1<=N,M<=100）的土地，雨后积起了水，有水标记为‘$’，干燥为‘#’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？（八连通区域指的是从区域内每一位置出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合，在不越出区域的前提下，到达区域内的任意位置。)
【样例输入】
10 12
$########$$#
#$$$#####$$$
####$$###$$#
#########$$#
#########$##
##$######$##
#$#$#####$$#
$#$#$####$$#
#$#$######$#
##$#######$#
【样例输出】
3
#include <iostream>
using namespace std;
struct node {
int x;
int y;
};
char map[][];
struct node que[];
int head,tail;
int book[][];
int sum;
int next[][] = {{,},{,},{,-},{-,},{-,},{,},{,-},{-,-}};//右下左上
int m,n,x,y,tx,ty; void bfs(int x,int y) {
sum++;
map[x][y] = ;
//初始化队列
head = ;
tail = ;
que[tail].x = x;
que[tail].y = y;
book[x][y] = ;
tail++;
while(head < tail) {
for(int k = ; k < ; k++) {
tx = que[head].x + next[k][];
ty = que[head].y + next[k][];
if(tx < || tx >= m || ty < || ty >= n) {
continue;
}
if(map[tx][ty] == '$' && book[tx][ty] == ) {
map[tx][ty] = '#';
book[tx][ty] = ;
que[tail].x = tx;
que[tail].y = ty;
tail++;
}
}
head++;
}
}
int main() {
cin >> m>>n;
for(int i = ; i <m; i++) {
for(int j = ; j < n; j++) {
cin >> map[i][j];
}
}
for(int i = ; i <m; i++) {
for(int j = ; j < n; j++) {
if(map[i][j] == '$') {
bfs(i,j);
}
}
}
cout <<sum << endl;
return ;
}
3、迷宫问题
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
【输入格式】
一个5 * 5的二维数组，表示一个迷宫。数据保证有唯一解。
【输出格式】
左上角到右下角的最短路径，格式如样例所示。
【样例输入】
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【样例输出】
（0，0）
（1，0）
（2，0）
（2，1）
（2，2）
（2，3）
（2 , 4）
（3 , 4）
（4，4）
#include <iostream> using namespace std;
int h[][],b[];
int xx[] = {-,,,},yy[] = {,,-,};
bool a[][];
int main(){
int t = ,w = ,x,y,k = ;
for(int i = ;i < ;i++){
for(int j = ;j < ;j++){
cin >> a[i][j];
}
}
h[][] = ;
h[][] = ;
a[][] = ;
do{
t++;
for(int i =;i < ;i++){
x = h[t][] + xx[i];
y = h[t][] + yy[i];
if(x >= && x < && y >= && y < && a[x][y] == ){
a[x][y] = ;
w++;
h[w][] = t;
h[w][] = x;
h[w][] = y;
if(x == && y == )
break;
}
} }while(t < w);
while(w > ){
k++;
b[k] = w;
w = h[w][];
}
cout << "(0,0)" << endl;
for(int i = k;i >= ;i--)
cout << "(" << h[b[i]][] << "," << h[b[i]][] << ")" << endl;
return ;
}