NC220162. 跑步
描述
NIT走到了一片森林，这片森林可以抽象成一个n*m的矩阵。有一些地方长有树，NIT不能走到上面去。NIT可以上下左右或斜向八连通行走。
现在NIT想跑跑步锻炼身体，他想沿着一条路走然后回到起点。并且NIT想这条路径一定是一个至少包着一颗树的环。请问这条路径的最短长度是多少。
输入描述
第一行有三个整数n,m,q表示森林的长宽以及询问个数
接下来n行,每行m个字符,表示森林的情况。其中”.”表示空地,”X”表示树。
接下来q行每行两个数x，y表示NIT的起点（起点不会是树）保证有合法路径。
输出描述
输出q行，每行表示每个询问的最短路长度
示例1
输入:
6 7 3 ....... ...X.X. ...X.X. ...XXX. .X..... ....... 1 7 3 7 3 1
输出:
13 12 6
说明:
C++(clang++11) 解法, 执行用时: 191ms, 内存消耗: 8268K, 提交时间: 2021-04-09 20:22:25
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=1005;
int a[MAXN][MAXN],s[MAXN][MAXN];
queue<int>q;
inline void sss(int x,int y,int z) {
if(a[x][y]&&s[x][y]==0x3f3f3f3f) {
s[x][y]=z;
q.push(x<<15|y);
}
}
int main() {
int n,m,k,x,y;
cin>>n>>m>>k;
for(int i=1; i<=n; i++)for(int j=1; j<=m; j++) {
char c=getchar();
while(c!='.'&&c!='X')c=getchar();
if(c=='.')a[i][j]=1;
}
for(int i=1; i<=k; i++) {
int ans=0x3f3f3f3f;
cin>>x>>y;
memset(s,0x3f,sizeof(s));
s[x][y]=0;
q.push(x<<15|y);//将坐标x，y压到一个int里
while(!q.empty()) {
int u=q.front();
q.pop();
sss((u>>15)+1,(u&32767),s[u>>15][u&32767]+1);
sss((u>>15)+1,(u&32767)+1,s[u>>15][u&32767]+1);
sss((u>>15),(u&32767)+1,s[u>>15][u&32767]+1);
sss((u>>15)-1,(u&32767)+1,s[u>>15][u&32767]+1);
sss((u>>15)-1,(u&32767),s[u>>15][u&32767]+1);
sss((u>>15)-1,(u&32767)-1,s[u>>15][u&32767]+1);
sss((u>>15),(u&32767)-1,s[u>>15][u&32767]+1);
sss((u>>15)+1,(u&32767)-1,s[u>>15][u&32767]+1);
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(s[i][j]>s[i-1][j-1]||s[i][j]>s[i-1][j]||s[i][j]>s[i-1][j+1])
if(s[i][j]>s[i+1][j-1]||s[i][j]>s[i+1][j]||s[i][j]>s[i+1][j+1])
if(s[i][j]<=s[i][j+1]&&s[i][j]<=s[i][j-1])
ans=min(ans,s[i][j]*2);
if(s[i][j]>s[i-1][j+1]||s[i][j]>s[i][j+1]||s[i][j]>s[i+1][j+1])
if(s[i][j]>s[i-1][j-1]||s[i][j]>s[i][j-1]||s[i][j]>s[i+1][j-1])
if(s[i][j]<=s[i+1][j]&&s[i][j]<=s[i-1][j])
ans=min(ans,s[i][j]*2);
if(s[i][j]==s[i][j-1]&&s[i][j]<=s[i+1][j]&&s[i][j]<=s[i+1][j-1]&&s[i][j]<=s[i-1][j]&&s[i][j]<=s[i-1][j-1])ans=min(ans,s[i][j]*2+1);
if(s[i][j]==s[i+1][j-1]&&s[i][j]<=s[i][j-1]&&s[i][j]<=s[i+1][j])ans=min(ans,s[i][j]*2+1);
if(s[i][j]==s[i+1][j]&&s[i][j]<=s[i][j-1]&&s[i][j]<=s[i+1][j-1]&&s[i][j]<=s[i][j+1]&&s[i][j]<=s[i+1][j+1])ans=min(ans,s[i][j]*2+1);
if(s[i][j]==s[i+1][j+1]&&s[i][j]<=s[i][j+1]&&s[i][j]<=s[i+1][j])ans=min(ans,s[i][j]*2+1);
}
}
cout<<ans<<endl;
}
return 0;
}