P1605 迷宫
这是一道毒瘤题。。。
这是一道广搜题 bfs 。。。
注释：
1.memcpy（b,a,sizeof（a)）
把 a 的值全部复制给 b
memcpy（b，a，sizeof（int）*k）
把 a 中的 k 个元素复制给 b
头文件：#include<cstring>
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
int n,m,t,sx,sy,fx,fy,tx,ty,ans=;
bool vis[][]; //表示是否为墙
int dx[]={-,,,},
dy[]={,,-,};
struct pos //结构体 x代表横坐标，y代表纵坐标，used[][]代表是否走过
{
int x,y,used[][]; };
bool pan(int x,int y) //判断是否合法
{
return x>=&&x<=n&&y>=&&y<=m&&vis[x][y]==;
} pos sa;
void bfs()
{
queue<pos>q; //队列
sa.x=sx;
sa.y=sy;
sa.used[sx][sy]=; //标记已走
q.push(sa); //入队
while(!q.empty())
{
pos h=q.front();
q.pop(); //出队
for(int i=;i<=;i++)
{
int xx=h.x+dx[i];
int yy=h.y+dy[i];
if(h.used[xx][yy]||(!pan(xx,yy))) //不可以走
continue ;
if(xx==fx&&yy==fy) //到终点
{
ans++;
continue ;
} sa.x=xx;
sa.y=yy;
memcpy(sa.used,h.used,sizeof(h.used)); //鬼知道这是干什么哒（我知道了）注释1
sa.used[xx][yy]=;
q.push(sa); //新的入队 }
}
}
int main()
{
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(int i=;i<=t;i++)
{
cin>>tx>>ty;
vis[tx][ty]=;
} bfs(); //广搜 cout<<ans; return ; }
这还是一道深搜题 dfs 。。。
回顾一下递归回溯算法框架：
int search(int x,int y)
{
if(到目的地) 输出解;
else
for(int i=;i<=算符种数;i++)
{
if(符合条件)
{
保存结果;
search(下一层);
恢复：保存结果之前的状态{回溯};
}
}
}
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
int n,m,t,sx,sy,fx,fy,tx,ty,ans=;
bool vis[][];
int dx[]={-,,,},
dy[]={,,-,};
bool pan(int x,int y)
{
return x>=&&x<=n&&y>=&&y<=m&&vis[x][y]==;
} void dfs(int x,int y)
{
if(x==fx&&y==fy)
ans++; for(int i=;i<=;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(pan(xx,yy))
{
vis[xx][yy]=;
dfs(xx,yy);
vis[xx][yy]=;
}
}
}
int main()
{
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(int i=;i<=t;i++)
{
cin>>tx>>ty;
vis[tx][ty]=;
}
vis[sx][sy]=;
dfs(sx,sy); cout<<ans; return ; }