NC23486. 小A与小B
描述
输入描述
输出描述
如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。
示例1
输入:
4 5 . . . . . . # # # . . . . # D . . C # .
输出:
YES 3
Python3 解法, 执行用时: 886ms, 内存消耗: 27548K, 提交时间: 2023-01-17 15:26:35
from collections import deque
n,m=[int(x) for x in input().split()]
dirs=[[1,0],[-1,0],[0,1],[0,-1],[1,1],[-1,-1],[1,-1],[-1,1]]
g=[['']*m for i in range(n)]
vis = [[[0]*m for i in range(n)] for _ in range(2)]
q=[deque() for i in range(2)]
for i in range(n):
r=[x for x in input().split()]
for j in range(m):
if r[j]=='C':
q[0].append([i,j])
vis[0][i][j]=1
if r[j]=='D':
q[1].append([i,j])
vis[1][i][j]=1
g[i][j]=r[j]
def bfs(t):
for _ in range(len(q[t])):
i,j=q[t].popleft()
for k in range(4 if t else 8):
dx,dy=dirs[k]
x,y=i+dx,j+dy
if x<0 or x>=n or y<0 or y>=m or vis[t][x][y] or g[x][y]=='#': continue
if vis[1-t][x][y]: return 1
vis[t][x][y]=1
q[t].append([x,y])
return 0
def sol():
res = 0
while len(q[0]) or len(q[1]):
res+=1
if bfs(0): return res
if bfs(1): return res
if bfs(1): return res
return -1
ans = sol()
if ans==-1: print('NO')
else:
print('YES')
print(ans)
C++14(g++5.4) 解法, 执行用时: 59ms, 内存消耗: 6232K, 提交时间: 2020-06-04 11:41:17
#include<bits/stdc++.h>
using namespace std;
struct qw
{
int x,y;
}t;
int n,m,vis[2][1005][1005],step=0;
char a[1005][1005];
queue<qw> q[2];
int dx[]={0,0,1,-1,1,1,-1,-1},dy[]={1,-1,0,0,1,-1,1,-1};
void bfs(int w)
{
int len=q[w].size();
while(len--)
{
t=q[w].front();q[w].pop();
for(int i=0;i<4+(w==0?4:0);i++)
{
int bx=t.x+dx[i],by=t.y+dy[i];
if(bx>n||bx<1||by>m||by<1||vis[w][bx][by]||a[bx][by]=='#') continue;
vis[w][bx][by]=1;q[w].push((qw){bx,by});
if(vis[w^1][bx][by]) {cout<<"YES"<<endl<<step<<endl;exit(0);}
}
}
}
void solve()
{
while(step<=n*m)
{
step++;
bfs(0);
bfs(1);
bfs(1);
}
cout<<"NO"<<endl;
}
int main()
{
ios::sync_with_stdio(false);
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='C') q[0].push((qw){i,j}),vis[0][i][j]=1;
if(a[i][j]=='D') q[1].push((qw){i,j}),vis[1][i][j]=1;
}
solve();
}
C++11(clang++ 3.9) 解法, 执行用时: 33ms, 内存消耗: 4580K, 提交时间: 2019-04-14 13:17:26
#include<bits/stdc++.h>
using namespace std;
struct qw
{
int x,y;
}t;
int n,m,vis[2][1005][1005],step=0;
char a[1005][1005];
queue<qw> q[2];
int dx[]={0,0,1,-1,1,1,-1,-1},dy[]={1,-1,0,0,1,-1,1,-1};
void bfs(int w)
{
int len=q[w].size();
while(len--)
{
t=q[w].front();q[w].pop();
for(int i=0;i<4+(w==0?4:0);i++)
{
int bx=t.x+dx[i],by=t.y+dy[i];
if(bx>n||bx<1||by>m||by<1||vis[w][bx][by]||a[bx][by]=='#') continue;
vis[w][bx][by]=1;q[w].push((qw){bx,by});
if(vis[w^1][bx][by]) {cout<<"YES"<<endl<<step<<endl;exit(0);}
}
}
}
void solve()
{
while(step<=n*m)
{
step++;
bfs(0);
bfs(1);
bfs(1);
}
cout<<"NO"<<endl;
}
int main()
{
ios::sync_with_stdio(false);
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='C') q[0].push((qw){i,j}),vis[0][i][j]=1;
if(a[i][j]=='D') q[1].push((qw){i,j}),vis[1][i][j]=1;
}
solve();
}