POJ 2049 Finding Nemo(3 D BFS)
タイトルアドレス:http://poj.org/problem?id=2049
この問題は1日WAでしたが、結局C++をG++に変更して過ぎました.なぜか分かりません.
この構想は,各メッシュの座標をメッシュの左下角座標に置き換え,メッシュの上と右を3次元で表すことである.
そしてBFS検索は、全て検索して最小値をとります.
この問題は1日WAでしたが、結局C++をG++に変更して過ぎました.なぜか分かりません.
この構想は,各メッシュの座標をメッシュの左下角座標に置き換え,メッシュの上と右を3次元で表すことである.
そしてBFS検索は、全て検索して最小値をとります.
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
struct node
{
int x, y, ans;
};
int mp[220][220][3], vis[220][220];/*mp ，0 ，1 ，2 ， 0 ，1 */
int jx[]= {0,0,1,-1};
int jy[]= {1,-1,0,0};
int min1;
void bfs(int s, int t)
{
int i, j;
queue<node>q;
node f1, f2;
f1.x=s;
f1.y=t;
f1.ans=0;
vis[s][t]=1;
q.push(f1);
min1=10000000;
while(!q.empty())
{
f1=q.front();
q.pop();
//if(f1.x<=4&&f1.y<=4)
//printf("%d %d %d
",f1.x, f1.y, f1.ans);
if(f1.x>=199||f1.y>=199||f1.x==0||f1.y==0)
{
if(min1>f1.ans)
{
min1=f1.ans;
}
continue ;
}
if(f1.ans>=min1)
continue ;
f2.x=f1.x+jx[0];
f2.y=f1.y+jy[0];
if(!vis[f2.x][f2.y]&&mp[f1.x][f1.y][0]!=2)//
{
if(mp[f1.x][f1.y][0]==1)
f2.ans=f1.ans+1;
else
f2.ans=f1.ans;
vis[f2.x][f2.y]=1;
q.push(f2);
}
f2.x=f1.x+jx[1];
f2.y=f1.y+jy[1];
if(!vis[f2.x][f2.y]&&mp[f2.x][f2.y][0]!=2)//
{
if(mp[f2.x][f2.y][0]==1)
f2.ans=f1.ans+1;
else
f2.ans=f1.ans;
vis[f2.x][f2.y]=1;
q.push(f2);
}
f2.x=f1.x+jx[2];
f2.y=f1.y+jy[2];
if(!vis[f2.x][f2.y]&&mp[f1.x][f1.y][1]!=2)//
{
if(mp[f1.x][f1.y][1]==1)
f2.ans=f1.ans+1;
else
f2.ans=f1.ans;
vis[f2.x][f2.y]=1;
q.push(f2);
}
f2.x=f1.x+jx[3];
f2.y=f1.y+jy[3];
if(!vis[f2.x][f2.y]&&mp[f2.x][f2.y][1]!=2)//
{
if(mp[f2.x][f2.y][1]==1)
f2.ans=f1.ans+1;
else
f2.ans=f1.ans;
vis[f2.x][f2.y]=1;
q.push(f2);
}
}
}
int main()
{
int n, m, i, j, a, b, c, d;
double x, y;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==-1&&m==-1) break;
memset(mp,0,sizeof(mp));
for(i=0; i<n; i++)
{
scanf("%d%d%d%d",&a, &b, &c, &d);
if(c)
{
for(j=0; j<d; j++)
{
mp[a-1][b+j][1]=2;
//printf("%d %d 0
",a-1,b+j);
}
}
else
{
for(j=0; j<d; j++)
{
mp[a+j][b-1][0]=2;
//printf("%d %d 1
",a+j,b-1);
}
}
}
for(i=0; i<m; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c)
{
mp[a-1][b][1]=1;
}
else
{
mp[a][b-1][0]=1;
}
}
scanf("%lf%lf",&x,&y);
a=x;
b=y;
if(a>=199||b>=199||a<=0||b<=0)
{
printf("0
");
continue ;
}
memset(vis,0,sizeof(vis));
bfs(a,b);
if(min1==10000000)
printf("-1
");
else
printf("%d
",min1);
}
return 0;
}