搜索和动态规划是算法界的两座大山。
搜索本质上是一种遍历，是对每一种情况操作一遍。
T1 迷宫（dfs）
是好题，一道用dfs的好题。
#include <iostream>
#include <cstring>
using namespace std;
int n,m,t;
int movex[5]={0,1,0,-1,0};//右 上
int movey[5]={0,0,-1,0,1};//左 下
int world[15][15];//图
int vis[15][15];//标记
int sx,sy,fx,fy;//起点 终点
int cnt;//计数。
void dfs(int x,int y){
if(x==fx&&y==fy){
cnt++;
return;
}
for(int i=1;i<=4;i++){
int nx=x+movex[i];
int ny=y+movey[i];
if(world[nx][ny]==1&&vis[nx][ny]==0){//可以走到。
vis[nx][ny]=1;
dfs(nx,ny);
vis[nx][ny]=0;
}
}
}
int main(){
memset(vis,0,sizeof(vis));
memset(world,0x3f,sizeof(world));//默认不能走。
cin>>n>>m>>t;
for(int i=1;i<=n;i++){
for(int l=1;l<=m;l++){
world[i][l]=1;//可以走的。
}
}
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=t;i++){
int x1,y1;
cin>>x1>>y1;
world[x1][y1]=0x3f;//障碍。
}
vis[sx][sy]=1;
dfs(sx,sy);
cout<<cnt;
return 0;
}T2 马的遍历
是好题，一道用bfs的好题。
非常愚笨的手写队列。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2e5;
struct note{
int x;//横坐标。
int y;//纵坐标。
int step;//步数。
};
note point[N];
int movex[9]={0,2, 2, 1, 1,-1,-1,-2,-2};
int movey[9]={0,1,-1, 2,-2, 2,-2, 1,-1};
int world[405][405];
int step[405][405];
bool vis[405][405];
int n,m;
int mx,my;
int main(){
memset(world,0x3f,sizeof(world));//
memset(step,0,sizeof(step));//特判
cin>>n>>m;//输入N M。
cin>>mx>>my;//输入起点。
for(int i=1;i<=n;i++){
for(int l=1;l<=m;l++){
world[i][l]=1;//能走的点。
}
}
//step前+1 = step后。
int head=1,tail=1;
point[head].x = mx;
point[head].y = my;//起点？？
vis[mx][my]=true;
tail++;
while(head<tail){
for(int i=1;i<=8;i++){
int cur_x=point[head].x+movex[i];//移动后的横坐标。
int cur_y=point[head].y+movey[i];//移动后的纵坐标。
if(cur_x<=0||cur_y<=0) continue;//防止数组越界。
if(world[cur_x][cur_y]==1&&vis[cur_x][cur_y]==false){//可以走 且 没走过。
point[tail].x=cur_x;//记录横坐标。
point[tail].y=cur_y;//记录纵坐标。
vis[cur_x][cur_y]=true;//这个点已经走过了。
step[cur_x][cur_y]=step[point[head].x][point[head].y]+1;//从开始遍历八个方向的点的STEP+1。
tail++;//记录 入列。
//cout<<"step head: "<<step[point[head].x][point[head].y]<<endl;
//cout<<"step cur : "<<step[cur_x][cur_y]<<endl<<endl;
}
}
head++;//遍历完成。
}
for(int i=1;i<=n;i++){
for(int l=1;l<=m;l++){
if(step[i][l]==0){
step[i][l]=-1;//仍然为0的点。
}
}
}
step[mx][my]=0;//起点为0。
for(int i=1;i<=n;i++){
for(int l=1;l<=m;l++){
cout<<step[i][l]<<" ";
}
cout<<endl;
}
return 0;
}待续............。