细节多恶心广搜求调 QAQ
查看原帖
细节多恶心广搜求调 QAQ
372172
Q__A__Q楼主2022/11/7 23:37
// Problem: P1126 机器人搬重物
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1126
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2022-11-05 23:34:50
// Author: fzy
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn=60;
const int inf=1e9+7;
const int ds[]={3,2,1,3,1};
int ansr,n,m,mp[maxn][maxn],s1,s2,e1,e2,pos,vis[maxn][maxn][maxn][maxn],ans[maxn][maxn][5],vis2[maxn][maxn][5][5];

struct node {
	int x,y,pos;
};

inline int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

queue<node> q;
inline void bfs(int x,int y,int pos) {
	ans[x][y][pos]=0;
	q.push(node{x,y,pos});
	while(!q.empty()) {
		node u=q.front();
		q.pop();
		int xn=u.x,yn=u.y,posn=u.pos;
		if(ans[xn][yn][posn]>=ansr&&ans[xn][yn][posn]!=0x7f7f) continue;
		if(xn==e1&&yn==e2) {
			ansr=min(ansr,ans[xn][yn][posn]);
//			cout<<ansr<<endl;
			continue;
		}
		// for(int j=0;j<2;++j) {
			// int post=(posn+dpos[j])%4;
			for(int i=0;i<5;++i) {
				int post=posn,xt=xn,yt=yn;
				if(i<=3) {	
					if(posn==0) {
						xt=xn+ds[i];
					}
					else if(posn==2) {
						xt=xn-ds[i];
					}
					else if(posn==1) {
						yt=yn+ds[i];
					}
					else if(posn==3) {
						yt=yn-ds[i];
					}
				}
				else {
					post=(posn+ds[i])%4;
				}
				if(xt>n||xt<1||yt>m||yt<1) continue;
				if(mp[xt][yt]==1) continue;
				if(vis[xt][yt][xn][yn]) continue;
				if(vis2[xt][yt][post][posn]) continue;
				if(xt!=xn&&yt!=yn) vis[xt][yt][xn][yn]=1,vis[xn][yn][xt][yt]=1;
				vis2[xt][yt][post][posn]=vis2[xt][yt][posn][post]=1;
//				cout<<xt<<' '<<yt<<endl;
				if(xt==5&&yt==2) {
					cout<<ans[xt][yt][0]<<' '<<xn<<' '<<yn<<' '<<i<<endl;
				}
				ans[xt][yt][post]=min(ans[xt][yt][post],ans[xn][yn][posn]+1);
				q.push(node{xt,yt,post});
			}
		// }
	}
}

signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    n=read(),m=read();
    memset(mp,0,sizeof mp);
    for(int i=1;i<=n;++i)
    	for(int j=1;j<=m;++j) {
    		int x=read();
    		if(x==1)
    			mp[i][j]=mp[i][j+1]=mp[i+1][j]=mp[i+1][j+1]=1;
    	}
    // for(int i=1;i<=n+1;i++) {
    	// for(int j=1;j<=m+1;++j)
    		// cout<<mp[i][j]<<' ';
    	// puts("");
    // }
    memset(ans,0x7f7f,sizeof ans);
    s1=read(),s2=read(),e1=read(),e2=read();
    s1++,s2++,e1++,e2++;	
    char ch;
    cin>>ch;
    if(ch=='N') pos=0;
    else if(ch=='E') pos=1;
    else if(ch=='S') pos=2;
    else pos=3;
    ansr=inf;
    bfs(s1,s2,pos);
//    cout<<ans[8][2][3]<<' '<<ans[8][2][0]<<' '<<ans[5][2][0]<<' '<<endl;
    write(ansr);
    return 0;
}

vis2[a][b][c][d]判断a,b方向c旋转到d是否有重复

vis[a][b][c][d]判断a,b走动到c,d是否有重复

mp用来处理点是否合法

2022/11/7 23:37
加载中...