#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define lowbit(x) x & -x
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
I int read() {
int s = 0 , w = 1; char ch = getchar();
while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
return s * w;
}
I char rd() {
char ch = getchar();
while(ch != '.' && ch != '#' && ch != 'C' && ch != 'D') ch = getchar();
while(ch == '.' || ch == '#' || ch == 'C' || ch == 'D') return ch;
}
const int N = 1005;
struct point {
int x , y;
};
queue <point> q[2];
int n , m ;
int dis[N][N];
bool used[N][N][2];
char s[N][N];
int tx , ty , sx , sy;
int dx[8] = {1 , 0 , -1 , 0 , 1 , 1 , -1 , -1};
int dy[8] = {0 , 1 , 0 , -1 , 1 , -1 , 1 , -1};
int bfs() {
memset(dis , -1 , sizeof(dis));
q[0].push((point){sx , sy});
q[1].push((point){tx , ty});
dis[sx][sy] = dis[tx][ty] = 0;
used[sx][sy][0] = used[tx][ty][1] = 1;
for(int tmp = 0 ; ; ++ tmp) {
if(q[0].empty() || q[1].empty()) return -1;
// printf("%d**\n" , tmp);
// For(i , 0 , n - 1){
// For(j , 0 , m - 1) printf("%3d " , dis[i][j]) ; putchar('\n');
// }
if(tmp % 3 == 0) {
point u = q[0].front() , v; q[0].pop();
For(i , 0 , 7) {
v.x = u.x + dx[i] , v.y = u.y + dy[i] ;
if(v.x < 0 || v.x >= n || v.y < 0 || v.y >= m || s[v.x][v.y] == '#' || used[v.x][v.y][0]) continue;
used[v.x][v.y][0] = 1;
if(dis[v.x][v.y] >= 0) return tmp / 3 + 1;
dis[v.x][v.y] = dis[u.x][u.y] + 1;
q[0].push(v);
}
} else {
For(k , 1 , 2) {
point u = q[1].front() , v; q[1].pop();
For(i , 0 , 3) {
v.x = u.x + dx[i] , v.y = u.y + dy[i] ;
if(v.x < 0 || v.x >= n || v.y < 0 || v.y >= m || s[v.x][v.y] == '#' || used[v.x][v.y][1]) continue;
used[v.x][v.y][1] = 1;
if(dis[v.x][v.y] >= 0) {
//printf("find the answer : %d %d\n" , v.x , v.y);
return tmp / 3 + 1;
}
dis[v.x][v.y] = dis[u.x][u.y] + 1;
q[1].push(v);
}
}
}
}
return -1;
}
signed main() {
n = read() , m = read() ;
For(i , 0 , n - 1)
For(j , 0 , m - 1) cin >> s[i][j];
For(i , 0 , n - 1)
For(j , 0 , m - 1) {
if(s[i][j] == 'C') sx = i , sy = j;
if(s[i][j] == 'D') tx = i , ty = j;
}
int ans = bfs();
if(ans == -1) {
puts("NO");
} else printf("YES\n%d\n" , ans);
return 0;
}
/*
4 5
.....
.###.
...#D
..C#.
*/
代码调不出来一直WA,求救!!!!!!
全部评论
(1) 回帖