关于P1825 #8数据 初学者不知道问题在哪 违规自杀 ┭┮﹏┭┮
  • 板块灌水区
  • 楼主Bread_m
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/11/17 21:05
  • 上次更新2023/10/27 02:36:20
查看原帖
关于P1825 #8数据 初学者不知道问题在哪 违规自杀 ┭┮﹏┭┮
362558
Bread_m楼主2022/11/17 21:05

注:程序已A,但是其实我并没有对

搜索初学蒻鸡,自测数据对比发现的问题,无法自解

本人代码如下

#include<bits/stdc++.h> 
using namespace std;
char mp[302][302]; 
int mmp[302][302];
bool bj[302][302];
int d[100000][2],
    dx[4]={-1,1,0,0},
    dy[4]={0,0,-1,1};
int n,m;

int change(int &x,int &y)
{
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			if(!(i==x&&j==y))
			{
				if(mp[i][j]==mp[x][y])
				{

					x=i;
					y=j;
					return 0;
				}
			}
		}
	}
}
bool asd[26];
void bfs(int x,int y){
	int head=0,tail=1;
	d[tail][0]=x,d[tail][1]=y;
	bj[x][y]=true;
	do{
		head++;
		int xn=d[head][0],yn=d[head][1];
		if(mp[xn][yn]>='A'&&mp[xn][yn]<='Z'){
			int z=mmp[xn][yn];

			change(xn,yn);

			mmp[xn][yn]=z;
		}
		for(int i=0;i<4;i++){
			int nx=xn+dx[i],ny=yn+dy[i];
			if((mp[nx][ny]!='#')&&(!bj[nx][ny])){
				bj[nx][ny]=true;
				tail++;
				d[tail][0]=nx;
				d[tail][1]=ny;
				mmp[nx][ny]=mmp[xn][yn]+1;
				if(mp[nx][ny]=='=') {
					cout << mmp[nx][ny];
					return ;
				}
				
			}
		}
		
		
	}while(head<tail);
}

int main(){
	cin >> n >> m;
	int x,y;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c; cin >> c;
			if(c=='@') x=i,y=j;
			mp[i][j]=c;
		}
	}
	bfs(x,y);
	return 0;
}

#8的数据如下

8 6
###=##
#..W.#
#....#
##@..#
#....#
#....#
#..W.#
######


依照本人设置的入队顺序 dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1}; 即 ↓ ↑ ← →的入队顺序 是没有问题的,跑出来的值图是酱紫:

000500
032440
021230
000120
021230
032340
043440
000000

完全没有问题,但如果把入队顺序换一下,如 dx[4]={1,-1,0,0}, dy[4]={0,0,-1,1};即 变为 ↑ ↓ ← →的入队顺序,跑出来就是:

000400
032340
021230
000120
021230
032340
043340
000000

可见,若非恰好在此数据下程序先从下方入队了传送门,我的程序会直接无视上方的传送门在第四步的时候就到达终点,不知道是什么问题....望各位大佬帮忙看看

┭┮﹏┭┮

2022/11/17 21:05
加载中...