取数游戏

题目描述： 一个 N×M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意 两个数字不相邻（若一个数字在另外一个数字相邻 8个格子中的一个即认为这两个数字相 邻），求取出数字和最大是多少。

输入

第一行有两个正整数 N 和 M ，表示了数字矩阵为 N行 M 列。（ 1≤N,M≤6）

输出

输出一个整数，代表符合题目要求的最大的数字和。（样例确保数字和在int范围内）

输入复制

3 3

2 8 9

4 6 4

9 10 7

输出复制

27

#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int a[10][10]={0};
bool b[10][10]={0};
int n,m;
int ma=-1;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}func(1,1,0);cout<<ma;return 0;
}
void func(int x,int y,int sum)
{if(x==n&&y==m){ma=max(ma,sum);return;}int tx=x,ty=y;y++;if(y>m){x++;y=1;}if(b[x][y]==0){b[x][y]=1;b[x+1][y]=1;b[x-1][y]=1;b[x][y+1]=1;b[x][y-1]=1;b[x-1][y-1]=1;b[x-1][y+1]=1;b[x+1][y-1]=1;b[x+1][y+1]=1;func(x,y,sum+a[tx][ty]);b[x][y]=0;b[x+1][y]=0;b[x-1][y]=0;b[x][y+1]=0;b[x][y-1]=0;b[x-1][y-1]=0;b[x-1][y+1]=0;b[x+1][y-1]=0;b[x+1][y+1]=0;}func(x,y,sum);
}

走出迷宫的最少步数2

题目描述 ：当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫 地图，事情就会变得非常简单。假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点 到出口的最短路。

输入

第一行是两个整数n和m(1<=nm<=100)表示迷宫的行数和列数。接下来n行，每行一个长为m的字符串，表示整 个迷宫的布局。字符'.'表示空地，'#'表示墙，'S'表示起点 'T'表示出口。

输出

输出从起点到出口最少需要走的步数

输入复制

3 3

S#T

.#.

...

输出复制

6

#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int n,m;
char a[110][110];
bool b[110][110]={0};
int sx,sy;
int tx,ty;
int mi=9999999;
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];if(a[i][j]=='S'){sx=i;sy=j;}if(a[i][j]=='T'){tx=i;ty=j;}}}func(sx,sy,0);cout<<mi;return 0;
}
void func(int x,int y,int cnt)
{if(x==tx&&y==ty){mi=min(mi,cnt);return;}if(x+1<n&&a[x+1][y]!='#'&&b[x+1][y]==0){b[x+1][y]=1;func(x+1,y,cnt+1);b[x+1][y]=0;}if(x-1>=0&&a[x-1][y]!='#'&&b[x-1][y]==0){b[x-1][y]=1;func(x-1,y,cnt+1);b[x-1][y]=0;}if(y+1<m&&a[x][y+1]!='#'&&b[x][y+1]==0){b[x][y+1]=1;func(x,y+1,cnt+1);b[x][y+1]=0;}if(y-1>=0&&a[x][y-1]!='#'&&b[x][y-1]==0){b[x][y-1]=1;func(x,y-1,cnt+1);b[x][y-1]=0;}
}

小明学游泳

题目描述：小明想要学游泳。 这天，小明来到了游泳池，发现游泳池可以用N行M列的格子来表示，每个格子的面积都是1，且格子内水深相同。 由于小明刚刚入门，他只能在水深相同的地方游泳。为此，他把整个游泳池看成若干片区域，如果两个格子相邻 （上下左右四个方向）且水深相同，他就认为它们属于同一片区域。 小X想知道最大的一片区域面积是多少，希望你帮帮他。

 输入

第一行包含用一个空格隔开的两个整数N,M。（1≤N,M≤100） 接下来N行，每行包含M个 1到9的数字，表示每个格子的水深

输出

第一行包含一个整数，表示最大的一片区域面积。

样例

输入复制

3 3

1 2 4

2 2 4

1 5 2

输出复制

3

#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int a[110][110]={0};
bool b[110][110]={0};
int n,m;
int ma=-1;
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){func(i,j,1);}}cout<<ma;return 0;
}
void func(int x,int y,int cnt)
{b[x][y]=1;if(x+1<n&&a[x+1][y]==a[x][y]&&b[x+1][y]==0){func(x+1,y,cnt+1);}if(x-1<n&&a[x-1][y]==a[x][y]&&b[x-1][y]==0){func(x-1,y,cnt+1);}if(y+1<n&&a[x][y+1]==a[x][y]&&b[x][y+1]==0){func(x,y+1,cnt+1);}if(y-1<n&&a[x][y-1]==a[x][y]&&b[x][y-1]==0){func(x,y-1,cnt+1);}ma=max(ma,cnt);
}

小明学游泳2

题目描述：暑假快到啦，小明准备趁着这个暑假去学游泳。可是一开始小 X 就遇到了一个难题。 游泳池划分成了一个 n×m 的方格， 这里 n×m 表示 n 行 m 列。 因 为游泳池里的水深浅不一，所以这 n×m 个方格对 于小明的危险系数也会不一样。 而小 X 目前需要从左上角 的方格（1， 1）出发， 游到右下角 的方格（n， m），小明每次只 能从当前方格游到上下 左右四个相邻的方格中的某一格，并且在到达终点前不能离开游泳池。 小 X 很担心会发生什么危险，所以希望你能帮他找一条危险系数最小的路径。 一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。 注意：这条路径不能经过同一个方格两次（小 X 当然不希望去那么危险的地方再游一次）

输入

输入数据第一行有两个用空格隔开的正整数 n 和 m， 表示泳池的行数和列数。 接下来共有 n 行数据，每行有 m 个用空格隔开的大于等于 0 的整数， 表示每个方格 的危险系数

输出

输出仅有一行包含一个整数ans， 表示要求的从左上角的方格（ 1， 1）出发， 游到 右下角的方格（n， m） 的最小的危险系数。

输入复制

4 5

1 7 2 8 2

3 10 1 5 1

2 8 3 7 1

1 2 1 20 1

输出复制

19

#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int a[110][110]={0};
bool b[110][110]={0};
int n,m;
int mi=999999;
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}func(0,0,0);cout<<mi;return 0;
}
void func(int x,int y,int sum)
{b[x][y]=1;if(x==n-1&&y==m-1){sum=sum+a[x][y];mi=min(mi,sum);b[x][y]=0;return;}if(x+1<=n-1&&b[x+1][y]==0){func(x+1,y,sum+a[x][y]);}if(x-1>=0&&b[x-1][y]==0){func(x-1,y,sum+a[x][y]);}if(y+1<=m-1&&b[x][y+1]==0){func(x,y+1,sum+a[x][y]);}if(y-1>=0&&b[x][y-1]==0){func(x,y-1,sum+a[x][y]);}b[x][y]=0;
}