社区讨论
蒟蒻刚学OI求助??
P2199最后的迷宫参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi7ycz3j
- 此快照首次捕获于
- 2025/11/21 05:37 4 个月前
- 此快照最后确认于
- 2025/11/21 05:37 4 个月前
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int v[300][300];
char a[300][300];
int step[300][300];
int n,m;
int xp[4] = {0, 0, 1, -1};
int yp[4] = {1, -1, 0, 0};
void bfs(int x,int y,int fx,int fy) {
v[x][y] = 1;
int xx,yy,hx,hy;
queue<int>sx;
queue<int>sy;
sx.push(x);
sy.push(y);
while(!sx.empty()){
hx = sx.front();sx.pop();
hy = sy.front();sy.pop();
for(int i = 0;i < 4 ; i ++){
xx = hx + xp[i];
yy = hy + yp[i];
if(xx >=1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == 'O' && !v[xx][yy])
sx.push(xx);
sy.push(yy);
v[xx][yy] = 1;
step[xx][yy] = step[hx][hy] + 1;
int stepx,stepy;
stepx = xx; stepy = yy;
while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n && stepy <= m && !v[stepx][stepy]) {
stepx --; stepy ++;//东北
if(stepx == fx && stepy == fy){
cout << step[xx][yy] <<endl;
return;
}
}
stepx = xx; stepy = yy;
while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n && stepy <= m && !v[stepx][stepy]){
stepx --;//北
if(stepx == fx && stepy == fy){
cout << step[xx][yy] <<endl;
return;
}
}
stepx = xx; stepy = yy;
while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n && stepy <= m && !v[stepx][stepy]){
stepx --; stepy --;//西北
if(stepx == fx && stepy == fy){
cout << step[xx][yy] <<endl;
return;
}
}
stepx = xx; stepy = yy;
while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n && stepy <= m && !v[stepx][stepy]){
stepy --;//西
if(stepx == fx && stepy == fy){
cout << step[xx][yy] <<endl;
return;
}
}
stepx = xx; stepy = yy;
while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n && stepy <= m && !v[stepx][stepy]){
stepx ++; stepy --;//西南
if(stepx == fx && stepy == fy){
cout << step[xx][yy] <<endl;
return;
}
}
stepx = xx; stepy = yy;
while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n && stepy <= m && !v[stepx][stepy]){
stepx ++;//南
if(stepx == fx && stepy == fy){
cout << step[xx][yy] <<endl;
return;
}
}
stepx = xx; stepy = yy;
while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n && stepy <= m && !v[stepx][stepy]){
stepx ++; stepy ++;//东南
if(stepx == fx && stepy == fy){
cout << step[xx][yy] <<endl;
return;
}
}
stepx = xx; stepy = yy;
while(a[stepx][stepy] == 'O' && stepx >=1 && stepy >=1 && stepx <= n && stepy <= m && !v[stepx][stepy]){
stepy ++;//东
if(stepx == fx && stepy == fy){
cout << step[xx][yy] <<endl;
return;
}
}
}
}
cout << "Poor Harry" << endl;
return;
}
int main(){
int sx, sy, fx, fy;
cin >> n >> m;
for(int i = 1;i <= n; i ++){
for(int j = 1;j <= m ; j ++){
cin >> a[i][j];
}
}
while(scanf("%d%d%d%d", &fx, &fy, &sx, &sy)) {
if(fx == 0) break;
bfs(sx, sy, fx, fy);
}
return 0;
}
纯暴力过不了样例 QAQ
回复
共 1 条回复,欢迎继续交流。
正在加载回复...