成都市建设局权益卡网站,海洋聚创抖音代运营,建设网站必须要服务器吗,查公司查企业用什么软件题目大意#xff1a;小hi和小ho去咖啡厅喝咖啡#xff0c;咖啡厅可以看作是n * m的矩阵#xff0c;每个点要么为空#xff0c;要么被人、障碍物、椅子所占据#xff0c;小hi和小ho想要找两个相邻的椅子。起初两个人都在同一个点#xff0c;求两人到达满足要求的椅子所移动…题目大意小hi和小ho去咖啡厅喝咖啡咖啡厅可以看作是n * m的矩阵每个点要么为空要么被人、障碍物、椅子所占据小hi和小ho想要找两个相邻的椅子。起初两个人都在同一个点求两人到达满足要求的椅子所移动的最少步骤。 思路先BFS找出每个S到达每个椅子的最短路径长度然后遍历每一行和每一列找出最优解。 代码 #includecstdio
#includecstring
#includequeue
#includemap
#includecstdlib
#define INF 100000000
using namespace std;int n,m,d[10010],dir[4][2] {-1,0,1,0,0,-1,0,1};
bool vis[10010];
char ch[110][110];
queueintQ;void bfs(int sx,int sy){int i,j,k;for(i0;in;i)for(j0;jm;j){k i*m j;vis[k] false;d[k] INF; }k sx * m sy ; d[k] 0;while(!Q.empty())Q.pop();Q.push(k);while(!Q.empty()){int x Q.front();int tx x/m ;int ty x%m ; Q.pop();if(vis[x])continue;vis[x] true;for(i0;i4;i){int ex tx dir[i][0];int ey ty dir[i][1];if(ex0 || exn || ey0 || eym || ch[ex][ey] # || ch[ex][ey] P)continue;k ex*m ey;if(vis[k])continue;if(ch[ex][ey] S){d[k] d[k] d[x] 1 ? d[k] : d[x] 1;continue;}d[k] d[k] d[x] 1 ? d[k] : d[x] 1;Q.push(k);}}
}int main(){int i,j,p1,p2,ans,sx,sy;bool tag;while(scanf(%d%d,n,m) 2){ans INF;bool flag false;for(i0;in;i)scanf(%s,ch[i]);for(i0;in !flag;i)for(j0;jm !flag;j)if(ch[i][j] H){sx i;sy j;flag true;}bfs(sx,sy);int t1,t2;for(i0;in;i){p1 p2 INF ;for(j0;jm;j){if(ch[i][j] S){int temp d[i*mj];if(p1 INF)p1 temp;else if(p2 INF){p2 temp;ans ans p1 p2 ? ans : p1 p2 ;p1 p2;p2 INF ;}}else if(ch[i][j] P || ch[i][j] # || ch[i][j] .){p1 INF ;p2 INF ;}}}for(j0;jm;j){p1 p2 INF ;for(i0;in;i){if(ch[i][j] S){int temp d[i*mj];if(p1 INF)p1 temp;else if(p2 INF){p2 temp;ans ans p1 p2 ? ans : p1 p2 ;p1 p2;p2 INF ;}}else if(ch[i][j] P || ch[i][j] # || ch[i][j] .){p1 INF ;p2 INF ;}}}if(ans INF)printf(%d\n,ans);elseprintf(Hi and Ho will not have lunch.\n);}return 0;
} 转载于:https://www.cnblogs.com/jxgapyw/p/4845348.html
