社区讨论
求大佬指出代码错误
P2864[USACO06JAN] The Grove S参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi864o69
- 此快照首次捕获于
- 2025/11/21 09:15 4 个月前
- 此快照最后确认于
- 2025/11/21 09:15 4 个月前
CPP
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
//WARNING
#define int long long
//#define char unsigned char
//WARNING
#define F(x,y,z) for(int x=y;x<=z;x++)
#define D(x,y,z) for(int x=y;x>=z;x--)
#define all(x) x.begin(),x.end()
#define ini(x,y) memset(x,y,sizeof(x))
#define cint const int &
#define cauto const auto &
#define END fclose(stdin);fclose(stdout);
const int INF=0x3f3f3f3f3f3f3f3f;
const int MAXN=(static_cast<int>(1e2)+25);
inline int read()
{
int c=getchar(),x=0,y=1;
while(c>'9'||c<'0')
{
if(c=='-'){
y=-1;
}
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*y;
}
inline char getc(){
int c=getchar();
while(!((c>='a'&&c<='z')||(c>='A'&&c<='Z')||c=='#'||c=='.'||c=='*')){
c=getchar();
}
return static_cast<char>(c);
}
static int maze[MAXN][MAXN],dis[MAXN][MAXN],dis2[MAXN][MAXN];
struct node
{
int x,y,flag;
node(int x=0,int y=0,int flag=0):x(x),y(y),flag(flag) {}
};
static queue<node> q;
signed main(){
int r=read(),c=read(),sx=0,sy=0,line=0;
F(i,1,r){
F(j,1,c){
char ch=getc();
if(ch=='.'){
maze[i][j]=0;
}else{
if(ch=='*'){
maze[i][j]=0;
sx=i;
sy=j;
}else{
maze[i][j]=1;
line=(line==0)?j:line;
}
}
}
}
F(i,1,r){
if(maze[i][line]!=1){
maze[i][line]=-1;
}
}
q.push(node(sx,sy,0));
ini(dis,0x3f);
ini(dis2,0x3f);
dis[sx][sy]=0;
while(!q.empty()){
int x=q.front().x,y=q.front().y;
q.pop();
F(mx,-1,1){
F(my,-1,1){
if(mx==0&&my==0){
continue;
}
int x1=x+mx,y1=y+my;
if(dis[x1][y1]!=INF){
continue;
}
if(x1<=r&&x1>0&&y1>0&&y1<=c&&maze[x1][y1]!=1&&maze[x1][y1]!=-1){
dis[x1][y1]=dis[x][y]+1;
q.push(node(x1,y1,0));
}
}
}
}
q.push(node(sx,sy,0));
dis2[sx][sy]=0;
while(!q.empty()){
int x=q.front().x,y=q.front().y,flag=q.front().flag;
q.pop();
F(mx,-1,1){
F(my,-1,1){
if(mx==0&&my==0){
continue;
}
int x1=x+mx,y1=y+my;
if(dis2[x1][y1]!=INF){
continue;
}
if(x1<=r&&x1>0&&y1>0&&y1<=c&&maze[x1][y1]!=1){
if(flag==0){
if(maze[x1][y1]==-1){
dis2[x1][y1]=dis2[x][y]+1;
q.push(node(x1,y1,1));
}else{
dis2[x1][y1]=dis2[x][y]+1;
q.push(node(x1,y1,0));
}
}else{
if(maze[x1][y1]==-1){
continue;
}
dis2[x1][y1]=dis2[x][y]+1;
q.push(node(x1,y1,1));
}
}
}
}
}
int maxn=INF;
cout<<line<<endl;
F(i,1,r){
cout<<endl;
F(j,1,c){
printf("%20lld ",dis[i][j]);
}
}
F(i,1,r){
cout<<endl;
F(j,1,c){
printf("%20lld ",dis2[i][j]);
}
}
cout<<endl;
F(i,1,r){
if(maze[i][line]==1){
continue;
}
F(mx,-1,1){
F(my,-1,1){
int x1=i+mx,y1=line+my;
if(x1<=r&&x1>0&&y1>0&&y1<=c&&maze[x1][y1]!=1){
maxn=min(maxn,dis[x1][y1]+dis2[i][line]+1);
}
}
}
}
printf("%lld",maxn);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...