这道题宽搜是不是一定要用queue实现?
查看原帖
这道题宽搜是不是一定要用queue实现?
998474
ShaunJulian楼主2023/12/4 15:40

我用一个一维数组模拟队列,结果9个点RE

#include<bits/stdc++.h>
using namespace std;
int N,M;
char Map[301][301];
int drct[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct node{
	int x,y,n;
};
node line[999999];
int tx,ty;
struct nn{
	bool vis;
	int x,y;
};
struct mm{
	int x,y;
};
mm another[301][301];
nn temp[301];
int main()
{
	scanf("%d%d",&N,&M);
	int sx,sy;
	for(int i=1;i<=N;i++)
	for(int j=1;j<=M;j++)
	{
		cin>>Map[i][j];
		if(Map[i][j]=='@')
		{
			sx=i;
			sy=j;
		}
		if(Map[i][j]=='=')
		{
			tx=i;
			ty=j;
		}
		if(isupper(Map[i][j]))
		{
			if(!temp[Map[i][j]].vis)
			{
				temp[Map[i][j]].vis=true;
				temp[Map[i][j]].x=i;
				temp[Map[i][j]].y=j;
			}
			else
			{
				another[i][j].x=temp[Map[i][j]].x;
				another[i][j].y=temp[Map[i][j]].y;
				another[temp[Map[i][j]].x][temp[Map[i][j]].y].x=i;
				another[temp[Map[i][j]].x][temp[Map[i][j]].y].y=j;
			}
		}
	}
	int front=1,back=2;
	line[1].n=0;
	line[1].x=sx;
	line[1].y=sy;
	while(front<back)
	{
		if(!isupper(Map[line[front].x][line[front].y]))
		for(int i=0;i<4;i++)
		{
			if(Map[line[front].x+drct[i][0]][line[front].y+drct[i][1]]!='#')
	    	{
	    		line[back].x=line[front].x+drct[i][0];
	    		line[back].y=line[front].y+drct[i][1];
	    		line[back].n=line[front].n+1;
	    		cout<<"x="<<line[back].x<<" y="<<line[back].y<<endl;
	    		system("pause");
	    		if(line[back].x==tx&&line[back].y==ty)
	        	{
	    	    	printf("%d",line[back].n);
	    	    	return 0;
		    	}
		    	back++;
	    	}
		}
		else
		{
			for(int i=0;i<4;i++)
			{
				line[back].x=another[line[front].x][line[front].y].x+drct[i][0];
		    	line[back].y=another[line[front].x][line[front].y].y+drct[i][1];
		    	line[back].n=line[front].n+1;
		    	cout<<"x="<<line[back].x<<" y="<<line[back].y<<endl;
	    		system("pause");
		    	if(line[back].x==tx&&line[back].y==ty)
	        	{
	    	    	printf("%d",line[back].n);
	    	    	return 0;
			    }
			    back++;
			}
		}
		front++;
	}
	return 0;
}
/*
5 6
###=##
#.W.##
#.####
#.@W##
######
*/
/*
12 77
#############################################################################
#=A.#B.#C.#D.#E.#F.#G.#H.#I.#J.#K.#L.#M.#N.#O.#P.#Q.#R.#S.#T.#U.#V.#W.#X.#Y.#
#############################################################################
#YXWVUTSRQPONMLKJIHGFEDCBA#Z.......#...#...#...#...#...#...#...#...#...#....#
#.################################...#...#...#...#...#...#...#...#...#...##.#
#.#########################...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#....#.....#.....#...#.Z#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#..#..#..#..#..#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#...#.....#.....#.....#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
###########################.#.#.#.##...#...#...#...#...#...#...#...#...##.#.#
#@..........................#........#...#...#...#...#...#...#...#...#......#
#############################################################################
*/
2023/12/4 15:40
加载中...