60分WA求助
查看原帖
60分WA求助
785636
2022_37_yzyUUU楼主2024/11/29 17:15
#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
int n,m,bx,by,ex,ey,ans=INT_MAX;
char g[105][105];
int vis[105][105],gk[105][105];
int xx[]={0,1,-1,0,0};
int yy[]={0,0,0,1,-1};
void SetConsoleWindowSize(short x, short y) {
	char cmd[64];
	sprintf(cmd,"mode con cols=%d lines=%d",x,y);
	system(cmd);
}
struct node{
	int x,y,k,l;
	bool operator<(const node& a)const{
		return k<a.k;
	}
};
void bfs(){
	priority_queue<node> q;
	q.push({bx,by,-1,-1});
	vis[bx][by]=1;
	gk[bx][by]=-1;
	while(q.size()){node t=q.top();
		int tx=t.x,ty=t.y,tk=-t.k,tl=t.l;
		q.pop();
		if(tx==ex&&ty==ey){
			cout<<tk;
			return;
		}
		for(int i=1;i<=4;i++){
			int dl=tl,dk=gk[tx][ty],dx=tx+xx[i],dy=ty+yy[i];
			if(dx<1||dy<1||dx>n||dy>m||g[dx][dy]=='*'||vis[dx][dy])continue;
			vis[dx][dy]=1;
			if(i!=tl){
				dk++;
				dl=i;
				gk[dx][dy]=dk;
				q.push({dx,dy,-dk,dl});
			}else {
				gk[dx][dy]=dk;
				q.push({dx,dy,-dk,dl});
			}
		}
//		cout<<"\n";
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=m;j++){
//				cout<<gk[i][j];
//			}cout<<"\n";
//		}
//		Sleep(300);
	}
}
int main(){
//	SetConsoleWindowSize(200, 100);
//	freopen("P2937_2.in","r",stdin);
//	freopen("2.in","w",stdout);
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='C'){
				if(bx==0||by==0)
					bx=i,by=j;
				else 
					ex=i,ey=j;
			}
		}
	}
	bfs();
}
2024/11/29 17:15
加载中...