poj1101 openjudge 2802:小游戏

Sahar ·

更新时间:2024-09-21

· 637 次阅读

那真的是退化了
一个简单的bfs都调了这么久。。。

题意是有h*w的矩阵
里面有空格也有X
然后指定两个坐标（这两个坐标都一定有X）
问你相连这两个点最短的segments，就是连起来的线段数，（并不是步数
，你看看图就明白，一开始我也不是很理解样例）

真的毒瘤题

一开始就想用bfs走一遍然后记录，就想着应该bfs走的最短路径应该就是最短segment,没想到wa了

然后看了discuss
的确毒瘤在这里插入图片描述
上图是我画的我的代码后附的最后一组样例

这个也是测试数据里的一组真实数据

其实这个数据不全面，很多错误的只跑了一次目的地的程序都能跑对，只要你的方向顺序正确

http://poj.org/showmessage?message_id=176366
这是讨论里启发我的

然后我就知道不能只跑一遍目的地，要跑完全部的路取最小值

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define lson (o<<1)
#define rson (o<<1|1)
#define fi first
#define sc second
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define rg register
#define y1 yyyy
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
using namespace std;
const double pi=acos(-1);
const double eps=1e-6;
inline int lowbit(int x){return x&(-x);}
template inline A fpow(A x,B p,C yql){
	A ans=1;
	for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql;
	return ans;
}
inline int read()
{
    int X=0,w=1;
    char c=getchar();
    while(c'9')
    {
        if (c=='-')
        {
            w=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        X=(X<<3)+(X<9) w(x/10); putchar(x%10+'0'); }
int w,h;
char maze[80][80];
int x1,x2,y1,y2,ans;
bool in(int a,int b){
	return a=0&&b>=0&&b<=w+1;
}
struct node{
	int x,y,c,d;
};
void clear(queue& q) {
    queue empty;
    swap(empty, q);
}
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
bool vis[80][80];
void bfs(){
	if(abs(x1-x2)+abs(y1-y2)==1){
		ans=1;
		return ;
	}
	memset(vis,0,sizeof(vis));
	queueq;
	clear(q);
	q.push({x1+0,y1,0,-1});
/*	vis[x1][y1+1]=1;
	q.push({x1+0,y1-1,1,1});
	vis[x1][y1-1]=1;
	q.push({x1-1,y1+0,1,2});
	vis[x1-1][y1]=1;
	q.push({x1+1,y1+0,1,3});
	vis[x1+1][y1+1]=1;
*/
	while(!q.empty()){
		node now=q.front();
		q.pop();
		int xx=now.x,yy=now.y;
	//	cout<<"now:"<<xx<<" "<<yy<<" "<<now.c<<" "<<now.d<<endl;
		if(abs(xx-x2)+abs(yy-y2)==1){
			for(int i=0;i<4;i++){
				int tx=xx+dx[i],ty=yy+dy[i];
				if(tx==x2&&ty==y2){
					if(i==now.d){
						if(now.c<ans){
							ans=now.c;
						}
					}else {
						if(now.c+1<ans){
							ans=now.c+1;
						}
					}
				}
			}
		//	return;
		//	break;
		continue;
		}
		for(int i=0;i<4;i++){
			int tx=xx+dx[i],ty=yy+dy[i];
			if(in(tx,ty)&&!vis[tx][ty]&&maze[tx][ty]!='X'){
				if(now.d==-1){
					q.push({tx,ty,1,i});
				//	cout<<"push:"<<tx<<" "<<ty<<" "<<1<<" "<<i<<endl;
				}else {
					if(now.d!=i){
						q.push({tx,ty,now.c+1,i});
				//		cout<<"push:"<<tx<<" "<<ty<<" "<<now.c+1<<" "<<i<<endl;
					}else {
						q.push({tx,ty,now.c,i});
			//			cout<<"push:"<<tx<<" "<<ty<<" "<<now.c<<" "<<i<<endl;
					}
				}
				vis[tx][ty]=1;
			}
		}
	}
	//return 0;
}
void solve(){
	memset(maze,0,sizeof(maze));
	cin.getline(maze[0],100);
	for(int i=0;i>y1>>x1>>y2>>x2){
		if(x1==0&&x2==0&&y1==0&&y2==0){
			break;
		}
		ans=1e9;
		bfs();
		if(ans==1e9){
			cout<<"Pair "<<cnt<<": impossible."<<endl;
		}else {
			cout<<"Pair "<<cnt<<": "<<ans<<" segments."<>T;
	while(cin>>w>>h){
	//	getchar();
		if(w==0&&h==0){
			break;
		}
		cout<<"Board #"<<T<<":"<<endl;
		T++;
		solve();
		cout<<endl;
	}
	return 0;
}
/*
5 4
XXXXX
X   X
XXX X
 XXX 
2 3 3 4
0 0 0 0
0 0
2 2
XX
XX
1 1 2 2
7 6
XXXXXXX
X     X
X   X X
X X   X
X     X
XXXXXXX
1 4 7 3
0 0 0 0
*/

作者：离开那天

poj 小游戏

1024 个赞