@[djfyxjs](/user/1428267)
能放全代码吗
by 114514514htz @ 2024-08-21 16:14:05
```
#include<bits/stdc++.h>
using namespace std;
int n,g[1001][1001],ans;
char mapmap[1001][1001];
int startx,starty;
int endx,endy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int bfs(int x,int y){
if(x==endx&&y==endy) return ans;
g[x][y]=1;
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<=n&&xx>=1&&yy<=n&&yy>=1&&mapmap[xx][yy]=='0'&&g[xx][yy]!=1){
g[xx][yy]=1;
bfs(xx,yy);
ans++;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mapmap[i][j];
}
}
cin>>startx>>starty>>endx>>endy;
cout<<bfs(startx,starty);
return 0;
}
```
@[114514514htz](/user/974743)
by djfyxjs @ 2024-08-21 16:15:25
@[djfyxjs](/user/1428267) 深搜过不了，改好的深搜和我的代码都放在下面了
深搜
```cpp
#include<iostream>
using namespace std;
int n,g[1010][1010],ans = 1e9;
char mapmap[1010][1010];
int startx,starty;
int endx,endy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y,int num){
if(x==endx&&y==endy)
{
ans = min(ans,num);
return;
}
if(num>ans) return;
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<=n&&xx>=1&&yy<=n&&yy>=1&&mapmap[xx][yy] == '0'&&g[xx][yy] == 0){
g[xx][yy]=1;
dfs(xx,yy,num+1);
g[xx][yy]=0;
}
}
return;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mapmap[i][j];
}
}
cin>>startx>>starty>>endx>>endy;
g[startx][starty] = 1;
dfs(startx,starty,0);
cout<<ans;
return 0;
}
```
AC广搜
```cpp
#include<iostream>
#include<queue>
using namespace std;
const int N = 1e3+30;
int n,g[N][N];
char mapmap[N][N];
int startx,starty;
int endx,endy;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
struct node{
int x,y,ans;
};
queue<node> q;
int bfs(){
node a = {startx,starty,0};
g[startx][starty] = 1;
q.push(a);
while(!q.empty())
{
node p = q.front();
q.pop();
if(p.x == endx && p.y == endy) return p.ans;
for(int i=0;i<4;i++){
int xx=p.x+dx[i];
int yy=p.y+dy[i];
if(xx<=n&&xx>=1&&yy<=n&&yy>=1&&mapmap[xx][yy] == '0'&&g[xx][yy] == 0){
g[xx][yy]=1;
q.push(node{xx,yy,p.ans+1});
}
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mapmap[i][j];
}
}
cin>>startx>>starty>>endx>>endy;
cout<<bfs();
return 0;
}
```
by 114514514htz @ 2024-08-21 16:56:06
@[114514514htz](/user/974743)
阿里嘎多~（bushi）
by djfyxjs @ 2024-08-21 17:18:58
@[djfyxjs](/user/1428267)
看一下题目标签
by 114514514htz @ 2024-08-21 17:33:30