pku1376Robot
この主な経典の広捜、一般的な方法は1つの配列を定義して各位置の4つの面がアクセスされるかどうかを表して、それからキューですればいいです!ただ隣は歩けないので注意!コードは以下の通りです(他の人を参照すると、構造がはっきりしています!)
方法2、直接題意を満たす点をキューに入れ、最初の点を後ろに回してこそ意味があり、残りの点を後ろに回して浪費する.この方法ではキューが溢れやすく、私は何度もwaをして、何時間も調べて、最後にジャンプの次のポイントの要求を厳しくしました(次のポイントがジャンプしたことがないか、同じ歩数で到着したが方向が違うときだけキューに参加します)、過ぎました.
/*Problem: 1376 User: qjklw
Memory: 208K Time: 94MS
Language: C++ Result: Accepted
*/
#include <iostream>
#include <queue>
using namespace std;
#define maxint 51
struct Point
{
int x, y, length, face;
Point(int x1, int y1, int length1, int face1)
{
x=x1;
y=y1;
length=length1;
face=face1;
}
};
int g[maxint][maxint];
int v1x, v2x, v1y, v2y, ori, M, N;
int position[4][2]={{0,1}, {1,0}, {0,-1}, {-1, 0}} ;
bool visit[maxint][maxint][4];
void input()
{
int i, j, k ;
char a[10] ;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
scanf("%d",&g[i][j]) ;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
for(k=0; k<4; k++)
visit[i][j][k]=false;
scanf("%d%d%d%d", &v1x, &v1y, &v2x, &v2y) ;
v1x--, v2x--, v1y--, v2y--;
scanf("%s",a) ;
if(!strcmp(a,"south")) ori=1 ;
else if(!strcmp(a,"east")) ori=0 ;
else if(!strcmp(a,"west")) ori=2 ;
else ori=3 ;
}
void solve()
{
queue<Point> q;
Point p(v1x, v1y, 0, ori);
q.push(p) ;
int Length=-1, tx, ty, i, tlength, tface ;
while(!q.empty())
{
Point top=q.front();
if(top.x==v2x&&top.y==v2y)
{
Length=top.length;
break;
}
tx=top.x;
ty=top.y;
tlength=top.length;
for(i=-1; i<=1; i+=2)
{
tface=(top.face+i+4)%4 ;
if(visit[tx][ty][tface])
continue;
Point tp(tx, ty, tlength+1, tface) ;
q.push(tp) ;
visit[tx][ty][tface]=true ;
}
tface=top.face;
tlength=top.length;
for(i=1; i<=3; i++)
{
tx=top.x+i*position[tface][0];
ty=top.y+i*position[tface][1];
if(visit[tx][ty][tface])
continue;
if(tx<0||tx>=M-1||ty<0||ty>=N-1 || g[tx][ty]||g[tx+1][ty]||g[tx][ty+1]||g[tx+1][ty+1])
break;
Point tp(tx, ty, tlength+1, tface);
q.push(tp);
visit[tx][ty][tface]=true;
}
q.pop();
}
printf("%d
", Length) ;
}
int main()
{
while(scanf("%d%d", &M, &N))
{
if(!M&&!N) break ;
input() ;
solve() ;
}
return 0;
}方法2、直接題意を満たす点をキューに入れ、最初の点を後ろに回してこそ意味があり、残りの点を後ろに回して浪費する.この方法ではキューが溢れやすく、私は何度もwaをして、何時間も調べて、最後にジャンプの次のポイントの要求を厳しくしました(次のポイントがジャンプしたことがないか、同じ歩数で到着したが方向が違うときだけキューに参加します)、過ぎました.
/*Source Code
Problem: 1376 User: qjklw
Memory: 324K Time: 32MS
Language: C++ Result: Accepted
*/
#include <iostream>
using namespace std ;
const int maxint=10000;
struct Vertex
{
int x, y, length, face ;
}vertex[maxint] ;
int graph[51][51] ;
int way[4][3][2]={ {{0,1},{0,2},{0,3}}, {{1,0},{2,0},{3,0}}, {{0,-1},{0,-2},{0,-3}}, {{-1,0},{-2,0},{-3,0}}} ;
int M, N, v1x, v2x, v1y, v2y, ori ;
void input()
{
int i, j ;
char a[10] ;
for(i=0; i<M; i++)
for(j=0; j<N; j++)
scanf("%d",&graph[i][j]) ;
scanf("%d%d%d%d", &v1x, &v1y, &v2x, &v2y) ;
v1x--, v2x--, v1y--, v2y--;
scanf("%s",a) ;
if(!strcmp(a,"south")) ori=1 ;
else if(!strcmp(a,"east")) ori=0 ;
else if(!strcmp(a,"west")) ori=2 ;
else ori=3 ;
}
void solve()
{
int head=0, tail=0, i, k, m, n, p, flag=0;
if(v1x==v2x && v1y==v2y)
{
printf("0
") ;
return ;
}
vertex[head].x=v1x;
vertex[head].y=v1y;
vertex[head].face=ori;
vertex[head++].length=0;
while(head!=tail)
{
k=tail;
tail=(tail+1)%maxint;
for(i=0;i<3;i++)
{
m = vertex[k].x+way[vertex[k].face][i][0] ;
n = vertex[k].y+way[vertex[k].face][i][1] ;
p = vertex[k].length ;
if(graph[m+1][n]!=1||graph[m][n+1]!=1||graph[m+1][n+1]!=1|| m<M-1||m>=0 || n<N-1||n>=0)
break;
if(!graph[m][n]||(graph[m][n]==p+1&&graph[m][n]!=1))// ，
{
if(m==v2x && n==v2y)
{
printf("%d
", p+1) ;
return;
}
vertex[head].x=m;
vertex[head].y=n;
vertex[head].length=p+1;
vertex[head].face=vertex[k].face;
head=(head+1)%maxint;
}
else
break ;
}
if(!graph[vertex[k].x][vertex[k].y])
{
vertex[head].x=vertex[k].x; //
vertex[head].y=vertex[k].y;
vertex[head].length=vertex[k].length+1;
vertex[head].face=(vertex[k].face+1)%4;
head=(head+1)%maxint;
vertex[head].x=vertex[k].x; //
vertex[head].y=vertex[k].y;
vertex[head].length=vertex[k].length+1;
vertex[head].face=(vertex[k].face+3)%4;
head=(head+1)%maxint;
if(!flag)// ( ).
{
flag=1;
vertex[head].x=vertex[k].x;
vertex[head].y=vertex[k].y;
vertex[head].length=vertex[k].length+2;
vertex[head].face=(vertex[k].face+2)%4;
head=(head+1)%maxint;
graph[vertex[k].x][vertex[k].y]=2;
continue;
}
graph[vertex[k].x][vertex[k].y]=vertex[k].length+1;
}
}
printf("-1
") ;
}
int main()
{
while(scanf("%d%d", &M, &N))
{
if(!M&&!N) break ;
input() ;
solve() ;
}
return 0 ;
}