我是一只狗，叫做AC!

【算法分析】 求最少需要多少步，考虑使用广搜。从起点开始进行搜索，规则只能向上下左右走动，当搜索到终点时就结束。 【参考代码】 【时间复杂度】 O(n∗m)O(n*m)O(n∗m) 【预计得分】 100pts100pts100pts

代码如下： 其实我是用AI写的，信吗

#include <bits/stdc++.h> using namespace std; char MAP[109][109]; bool vis[109][109]; struct node { int x, y, step; }l,r; int dir[4][2] = { {-1,0} ,{0,1},{1,0},{0,-1} }; int main() { int n, m; cin >> n >> m; int sx, sy, tx, ty; for (int i = 1; i <= n; i++) { cin >> MAP[i] + 1; for (int j = 1; j <= m; j++) { if (MAP[i][j] == 'S') { sx = i, sy = j; } else if (MAP[i][j] == 'T') { tx = i, ty = j; } } } queue<node> q; q.push({ sx,sy,0 }); vis[sx][sy] = 1; while (q.size()) { r = q.front(); q.pop(); if (r.x == tx && r.y == ty) { cout << r.step; return 0; } for (int i = 0; i < 4; i++) { l.x = r.x + dir[i][0]; l.y = r.y + dir[i][1]; l.step = r.step + 1; if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= m && !vis[l.x][l.y] && MAP[l.x][l.y] != '#') { vis[l.x][l.y] = 1; q.push(l); } } } cout << -1; return 0; }

#include<iostream> #include<queue> #include<vector> using namespace std; struct node{ int x,y,step; }; int n,m,sx,sy,fx,fy,ax[5] = {0,1,-1,0,0},ay[5] = {0,0,0,1,-1}; queue<node> qu[2]; vector<vector<int> > ans; vector<vector<char> > mp; vector<vector<bool> > vis[2]; void input(){ cin >> n >> m; ans.resize(n + 5,vector<int>(m + 5,0)),mp.resize(n + 5,vector<char>(m + 5,' ')); vis[0].resize(n + 5,vector<bool>(m + 5,0)),vis[1].resize(n + 5,vector<bool>(m + 5,0)); for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ cin >> mp[i][j]; if(mp[i][j] == 'S') sx = i,sy = j; if(mp[i][j] == 'T') fx = i,fy = j; } } } bool check(int nx,int ny){ if(nx < 1 || ny < 1 || nx > n || ny > m) return 1; return 0; } void bfs(){ qu[0].push({sx,sy,0}),qu[1].push({fx,fy,0}); int flag = 0; vis[0][sx][sy] = 1,vis[1][fx][fy] = 1; while(!qu[0].empty() && !qu[1].empty()){ queue<node> &q = qu[flag]; int o_flag = (flag + 1) % 2; node r = q.front(); q.pop(); } int main(){ input(); bfs(); return 0; }

#include <iostream> #include <queue> using namespace std; char map[105][105]; int vis[105][105],wn,wm,sx,sy; int dir[4][2]={1,0,-1,0,0,1,0,-1}; int n,m; struct node{ int x,y,step; }; queue<node> q; void bfs(){ while(!q.empty()){ node t=q.front(); q.pop(); if(t.xwn && t.ywm){ cout<<t.step; return; } for(int i=0;i<4;i++){ int nx=t.x+dir[i][0]; int ny=t.y+dir[i][1]; if(nx<0 || nx>=n || ny<0 || ny>=m || map[nx][ny]'#' || vis[nx][ny]){ continue; } q.push({nx,ny,t.step+1}); vis[nx][ny]=1; } } cout<<-1; } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>map[i][j]; if(map[i][j]'S'){ sx=i; sy=j; } else if(map[i][j]=='T'){ wn=i; wm=j; } } } vis[sx][sy]=1; q.push({sx,sy,0}); bfs(); return 0; }

#include<bits/stdc++.h> using namespace std; int n,m; char a[118][118]; bool b[118][118]; int f[4][2]={-1,0,1,0,0,1,0,-1}; struct st { int x,y,l; }; queue <st> q; bool pd(int x,int y) { return x>0&&y>0&&x<=n&&y<=m&& a[x][y]!='#' && !b[x][y]; } int main() { cin>>n>>m; }

> 算法:BFS > 时间/内存:1ms/3.44mb > ->100pts<-[保熟得嘞!]

简简单单