T4WA90

我命由我不由天 · 2025 年1 月 30 日 14:42

题面：

我的代码：

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
I AK IOI;
int n,m,dx[]={0,1,0,-1},dy[]={1,0,-1,0};
char mapa[2005][2005];
struct node{
	int x,y;
}st,en;
int bfs(){
	queue<node>q;
	q.push({st.x,st.y});
	int vis[2005][2005];
	memset(vis,-1,sizeof vis);
	vis[st.x][st.y]=0;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==en.x&&t.y==en.y)return vis[t.x][t.y];
		for(int i=0;i<4;i++){
			int nx=t.x+dx[i],ny=t.y+dy[i];
			if(nx>0&&nx<=n&&ny>0&&ny<=m&&vis[nx][ny]==-1&&mapa[nx][ny]!='#'){
				vis[nx][ny]=vis[t.x][t.y]+1;
				q.push({nx,ny});
			}
		}
	}
	return -1;
}
int main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mapa[i][j];
			if(mapa[i][j]=='S'){
				st.x=i;
				st.y=j;
			}
			if(mapa[i][j]=='G'){
				en.x=i;
				en.y=j;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mapa[i][j]=='<')for(int k=1;k<=j;k++)if(mapa[i][k]=='.')mapa[i][k]='#';
			if(mapa[i][j]=='>')for(int k=j;k<=m;k++)if(mapa[i][k]=='.')mapa[i][k]='#';
			if(mapa[i][j]=='^')for(int k=1;k<=i;k++)if(mapa[k][j]=='.')mapa[k][j]='#';
			if(mapa[i][j]=='v')for(int k=i;k<=n;k++)if(mapa[k][j]=='.')mapa[k][j]='#';
		}
	}
	cout<<bfs();
	i_ak ioi;
}

WA90 的代码，我测的本地不输出？为什么在 xyd 会输出，并且为什么 90？

我命由我不由天 · 2025 年1 月 30 日 14:42

@王建力

黄飞栋 · 2025 年1 月 31 日 00:12

这里应该不能只判断mapa[nx][ny]!='#'，应该是mapa[nx][ny]=='.'

黄飞栋 · 2025 年1 月 31 日 00:44

举一个反例：

3 6
..G...
>>><<<
...S..

实际上要输出-1，而你的程序输出3

我命由我不由天 · 2025 年1 月 31 日 02:45

@黄飞栋 e你能解决一下我的代码本地不输出的原因吗？

黄飞栋 · 2025 年1 月 31 日 02:46

这个我也不太清楚

我命由我不由天 · 2025 年1 月 31 日 02:47

@黄飞栋你这里确定是mapa[nx][ny]!='.'？

黄飞栋 · 2025 年1 月 31 日 02:50

确定是，因为<、>这些符号本身也是视线范围内

我命由我不由天 · 2025 年1 月 31 日 02:52

@黄飞栋但是你这样判断不可走路径里S和G也被算上了呀，这肯定不对吧

我命由我不由天 · 2025 年1 月 31 日 02:53

@黄飞栋我考虑到了呀，代码里我也算上了呀，在for循环里面我就特殊的加上了

黄飞栋 · 2025 年1 月 31 日 02:53

改成 (mapa[nx][ny]=='.'||mapa[nx][ny]=='S'||mapa[nx][ny]=='G')试试

我命由我不由天 · 2025 年1 月 31 日 02:54

@黄飞栋等一下，我可能知道哪里错了，好像是for循环忘记特判了

黄飞栋 · 2025 年1 月 31 日 02:54

那你能帮我看看我的吗？

我命由我不由天 · 2025 年1 月 31 日 02:55

@黄飞栋看什么？等一下

黄飞栋 · 2025 年1 月 31 日 02:55

我命由我不由天 · 2025 年1 月 31 日 02:59

@黄飞栋等一下我之前的代码测试点6有问题，现在这是我的最新代码：

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
I AK IOI;
int n,m,dx[]={0,1,0,-1},dy[]={1,0,-1,0};
char mapa[2005][2005];
struct node{
	int x,y;
}st,en;
int bfs(){
	queue<node>q;
	q.push({st.x,st.y});
	int vis[2005][2005];
	memset(vis,-1,sizeof vis);
	vis[st.x][st.y]=0;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.x==en.x&&t.y==en.y)return vis[t.x][t.y];
		for(int i=0;i<4;i++){
			int nx=t.x+dx[i],ny=t.y+dy[i];
			if(nx>0&&nx<=n&&ny>0&&ny<=m&&vis[nx][ny]==-1&&mapa[nx][ny]!='#'){
				vis[nx][ny]=vis[t.x][t.y]+1;
				q.push({nx,ny});
			}
		}
	}
	return -1;
}
int main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mapa[i][j];
			if(mapa[i][j]=='S'){
				st.x=i;
				st.y=j;
			}
			if(mapa[i][j]=='G'){
				en.x=i;
				en.y=j;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mapa[i][j]=='<'){
				for(int k=1;k<j;k++)if(mapa[i][k]=='.')mapa[i][k]='#';
				mapa[i][j]='#';
			}
			if(mapa[i][j]=='>'){
				for(int k=j;k<m;k++)if(mapa[i][k]=='.')mapa[i][k]='#';
				mapa[i][j]='#';
			}
			if(mapa[i][j]=='^'){
				for(int k=1;k<i;k++)if(mapa[k][j]=='.')mapa[k][j]='#';
				mapa[i][j]='#';
			}
			if(mapa[i][j]=='v'){
				for(int k=i;k<n;k++)if(mapa[k][j]=='.')mapa[k][j]='#';
				mapa[i][j]='#';
			}
		}
	}
	cout<<bfs();
	i_ak ioi;
}

还是WA90 测试点6好了，但是测试点7有问题了 qwq

我命由我不由天 · 2025 年1 月 31 日 03:00

@黄飞栋哦哦哦，脑抽了，

我命由我不由天 · 2025 年1 月 31 日 03:01

@黄飞栋 okAC了， @栗子酱关帖

黄飞栋 · 2025 年1 月 31 日 03:02

请不要那么频繁的@ 别人

我命由我不由天 · 2025 年1 月 31 日 03:03

@黄飞栋 o知道了，因为有些人不@不来，所以我习惯@