如果你总是只通过86.67%的数据,那么需要注意(x1,y1) = (x2,y2)的情况,因为这种情况下这个格子无论如何也不能到达
很显然是一道BFS问题
有k个幽灵奇数秒在(x1,y1),偶数秒在(x2,y2),能不能从(1,1)走到(n,m)且求最少时间
那么对时间存储格子就有两种状态:
cin >> n >> m >> k;
for(int i = 1; i <= k; i ++){
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
exi[x1][y1][0] = 1;
exi[x2][y2][1] = 1;
}
exi[x1][y1][0]表示的是在 时间为奇数时,(x1,y1)会出现幽灵
exi[x2][y2][1]表示的时在 时间为偶数时,(x2,y2)会出现幽灵
在BFS中,我们需要结构体存储的信息是x, y, time, state:
x, y表示坐标信息
time表示从(1,1)到(x,y)的最少时间
state表示是否使用了时间静止
同时我们需要用vis[x][y][2]来表示(x,y)是否已经访问过了,要不然会重复访问
如果vis[x][y][0] = 0/1,那么表示(x,y)在没有使用时间静止的情况下(没有/有)访问过了
如果vis[x][y][1] = 0/1,那么表示(x,y)在已经使用了时间静止的情况下(没有/有)访问过了
这里需要用vis[x][y][0/1]两个状态来区分开(x,y)在是否使用时间静止条件下的状态
struct Node{
int x, y, time, state;
};
int exi[1010][1010][2];
int vis[1010][1010][2];
详细解释下核心部分:
int bfs(){
queue<Node> q;
q.push({1, 1, 0, 0});
while(q.size()){
Node now = q.front();
q.pop();
int nx = now.x, ny = now.y, ntime = now.time, nstate = now.state;
if(nx == n && ny == m) return ntime;
for(int i = 0; i < 4; i ++){
int x = nx + dx[i], y = ny + dy[i];
if(exi[x][y][0] && exi[x][y][1]) continue;
if(1 <= x && x <= n && 1 <= y && y <= m){
if(!nstate && exi[x][y][!(ntime & 1)]){
if(!vis[x][y][1]){
vis[x][y][1] = 1;
q.push({x, y, ntime + 1, 1});
}
}
else if(!exi[x][y][!(ntime & 1)] && !vis[x][y][nstate]){
vis[x][y][nstate] = 1;
q.push({x, y, ntime + 1, nstate});
}
}
}
}
return -1;
}
q.push({1, 1, 0, 0});
q.push({1, 1, 0, 0)}表示的是初始位置为(1,1)并且一开始时间为0, 状态为0(表示我没有使用时间静止)
if(exi[x][y][0] && exi[x][y][1]) continue;表示(x,y)无论如何也不能到达,直接跳过
if(!nstate && exi[x][y][!(ntime & 1)]){
if(!vis[x][y][1]){
vis[x][y][1] = 1;
q.push({x, y, ntime + 1, 1}); }
}
表示现在可以使用时间静止并且下一个点(x,y)时恰好会出现幽灵,那么我需要使用一次时间静止,这样就可以到达(x,y), 并且状态从0变为1
else if(!exi[x][y][!(ntime & 1)] && !vis[x][y][nstate]){
vis[x][y][nstate] = 1;
q.push({x, y, ntime + 1, nstate});
}
表示只要下一个点(x,y)不存在幽灵并且没有被访问过,那么可以直接到达
总代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
const int N = 1000010;
struct Node{
int x, y, time, state;
};
int exi[1010][1010][2];
int vis[1010][1010][2];
int n, m, k;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int bfs(){
queue<Node> q;
q.push({1, 1, 0, 0});
while(q.size()){
Node now = q.front();
q.pop();
int nx = now.x, ny = now.y, ntime = now.time, nstate = now.state;
if(nx == n && ny == m) return ntime;
for(int i = 0; i < 4; i ++){
int x = nx + dx[i], y = ny + dy[i];
if(exi[x][y][0] && exi[x][y][1]) continue;
if(1 <= x && x <= n && 1 <= y && y <= m){
if(!nstate && exi[x][y][!(ntime & 1)]){
if(!vis[x][y][1]){
vis[x][y][1] = 1;
q.push({x, y, ntime + 1, 1});
}
}
else if(!exi[x][y][!(ntime & 1)] && !vis[x][y][nstate]){
vis[x][y][nstate] = 1;
q.push({x, y, ntime + 1, nstate});
}
}
}
}
return -1;
}
signed main(){
HelloWorld;
cin >> n >> m >> k;
for(int i = 1; i <= k; i ++){
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
exi[x1][y1][0] = 1;
exi[x2][y2][1] = 1;
}
cout << bfs() << endl;
return 0;
}



京公网安备 11010502036488号