求高手帮看看这么计算为啥不行
查看原帖
求高手帮看看这么计算为啥不行
156042
王半仙楼主2024/8/30 08:56

高手能帮看看我这种方法有啥不对吗?

#include <bits/stdc++.h>
using namespace std;

const int Mx = 0x3f3f3f3f; 
struct Node{
	int x,y;
}; 
int dx[5] = {0,0,0,1,-1};
int dy[5] = {0,-1,1,0,0};
vector<Node> one[11][11];//一次可以走到哪些地方 
vector<Node> two[11][11];//两次可以走到哪些地方 
string tu[11];//地图 
bool book[11][11];//标记有没有走过 
int n,cx,cy,hx,hy;
int dis[11][11][11][11];//dis[i][j][k][l]表示Cuazyoxi在(i,j), Happybob在(k,l)需要的步数 
queue<Node> que;
bool flag; 

void bfs(int x,int y){
	for(int i=0;i<5;i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx<0||nx>=n||ny<0||ny>=n||tu[nx][ny]=='1')
			continue;
		one[x][y].push_back(Node{nx,ny});//一次走 
	}
	memset(book,false,sizeof(book));
	for(Node t:one[x][y]){
		for(int i=0;i<5;i++){
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			if(nx<0||nx>=n||ny<0||ny>=n||tu[nx][ny]=='1'||book[nx][ny])
				continue;
			two[x][y].push_back(Node{nx,ny});//两次走 
			book[nx][ny] = true;
		}
	}
}
//计算Cuazyoxi在(sx,sy), Happybob在(tx,ty)需要的步数
bool jisuan(int sx,int sy,int tx,int ty){
	int res = 0;
	for(Node i:one[sx][sy]){
		int ans = Mx;
		for(Node j:two[tx][ty]){
			//Happybob希望步数最少 
			ans = min(ans,dis[i.x][i.y][j.x][j.y]);
		}
		res = max(res,ans);//Cuazyoxi希望步数最多 
	}
	if(res == Mx)
		return false;
	dis[sx][sy][tx][ty] = min(dis[sx][sy][tx][ty],res+1);
	return true;
}

int main() {
	cin>>n>>cx>>cy>>hx>>hy;
	for(int i=0;i<n;i++)
		cin>>tu[i];
	memset(dis,0x3f,sizeof(dis));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(tu[i][j] != '1'){
				bfs(i,j);//计算从(i,j)走一次和走两次
				//两人在同一个点 
				dis[i][j][i][j] = 0;
			}
		}
	}
	while(true){
		flag = false;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(tu[i][j] == '1')
					continue;
				for(int k=0;k<n;k++){
					for(int l=0;l<n;l++){
						if(tu[i][j]=='1' || dis[i][j][k][l]!=Mx)
							continue;
						if(jisuan(i,j,k,l))
							flag = true;
					}
				}
			}
		}
		if(!flag) break; 
	}	
	if(dis[cx-1][cy-1][hx-1][hy-1] == Mx)
		cout<<"inf"<<endl;
	else	
		cout<<dis[cx-1][cy-1][hx-1][hy-1]<<endl;	
	return 0;
}
2024/8/30 08:56
加载中...