x
2025-07-29 17:10:26
发布于：上海
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char mp[50][50];
int vis[50][50];
int ans=1e9;
void dfs(int x,int y,int step){
if(xn&&ym){
ans=min(ans,step);
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(mp[nx][ny]=='@')continue;
if(nx>n||nx<1||ny>m||ny<1)continue;
if(vis[nx][ny]==1)continue;
vis[nx][ny]=1;
dfs(nx,ny,step+1);
vis[nx][ny]=0;
}
}
int main(){
freopen("tanxian.in","r",stdin);
freopen("tanxian.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
vis[1][1]=1;
dfs(1,1,0);
if(ans!=1e9){
cout<<ans;
}
else{
cout<<"0";
}
fclose(stdin);
fclose(stdout);
return 0;
}
全部评论 1
#include<bits/stdc++.h>
using namespace std;
bool vis[9][9];//定义vis数组，vis[i][j]标记(i,j)是否被访问过
bool MAP[9][9];//定义MAP数组，MAP[i][j]=false表示不是障碍物 MAP[i][j]=true是障碍物
int n, m, t, ans, sx, sy, fx, fy;//定义n,m,t,ans,sx,sy,ex,ey
int dir[4][2] = { 0,1,1,0,0,-1,-1,0 };//定义方向数组
void dfs(int x, int y) {//定义函数dfs(x,y)表示当前在(x,y)位置
if (x == fx && y == fy) { //判断是否xfx且yfy，判断是否到达终点
ans++;//路径数量+1
return; //返回
}for (int i = 0; i < 4; i++) {//for循环遍历方向数组 int nx = x + dir[i][0], ny = y + dir[i][1];//求出邻居位置(nx,ny) if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && MAP[nx][ny] == false) {//判断邻居是否在地图内且没有被访问过且不是障碍物，如果成立就走过去 vis[nx][ny] = 1;//vis[nx][ny]=1,标记(nx,ny)访问过 dfs(nx, ny);//去(nx,ny)的位置(从（nx，ny）开始搜索) vis[nx][ny] = 0;//vis[nx][ny]=0,(nx,ny)位置所有的方向都尝试过了， 回退，将(nx,ny)位置标记为未访问过 } }}
int main() {
freopen("shuliang.in", "r", stdin);
freopen("shuliang.out", "w", stdout);
cin >> n >> m >> t;//输入n，m，t
cin >> sx >> sy >> fx >> fy;//输入sx,sy,fx,fy
for (int i = 0; i < t; i++) {//for循环输入t个障碍物的位置并标记
int x, y;
cin >> x >> y;
MAP[x][y] =1;
}
vis[sx][sy] = 1;
dfs(sx,sy); //调用dfs(sx,sy),从(sx,sy)位置开始搜索
cout << ans;//输出答案
fclose(stdin);
fclose(stdout);
return 0;
}5天前 来自 上海
0
有帮助，赞一个