클래식 c 프로그램(0039) - 커브 횟수 구하기
/**************************************************************************************
* Function : test
* Create Date : 2014/07/14
* Author : NTSK13
* Email : [email protected]
* Copyright : , 。
* Version : V0.1
***************************************************************************************
c (0039) ---
:
Mr. Noh is responsible for enhancing the movement of a robot faster.
Now, Mr. Noh is thinking like this: The speed of the robot decreases when it changes its direction.
Therefore, it requires a study of the acceleration in direction changes.
However, the better method than that is to use the route with the minimum number of direction changes when it moves from point A to point B.
Because of that, he studies a maze.
When the maze information is given, he tries to create a program to move it from the starting point to the arriving point based on the minimized direction changes.
Let’s find out the minimum direction changes possible from the starting point to the arriving point when the maze information is given.
Time limit : 1 sec (Java : 2 sec)
[Input]
There can be more than one test case in the input file. The first line has T, the number of test cases.
Then the totally T test cases are provided in the following lines (T ≤ 10 )
In each test case, The width and height of the maze are given as N & M separately at the first row. (1 ≤ N, M ≤ 200)
The horizontal coordinate and vertical coordinate of the starting point, and the horizontal coordinate and vertical coordinate of the arriving point are given separately in order at the second row.
Information of the maze is given from the third row the number (N). At this time, the path indicates 0; the wall indicates 1. There is no blank each other.
[Output]
In case of being reachable from the starting point to the arriving point, generate the minimum direction change frequency between two points.
If not, generate "-1"
[Input Example]
2
7 7
1 2 7 5
1111111
0000011
1011001
1011100
1011110
1000000
1111111
7 7
1 2 7 6
1111111
0000001
1011000
1011100
1011110
1000000
1111111
[Output Example]
3
2
**************************************************************************************/
#include <stdio.h>
#define SIZE 201
#define MAXSIZE (SIZE * SIZE)
typedef struct
{
int x;
int y;
int change;
}Pos;
Pos start,end;
typedef struct
{
Pos store[MAXSIZE];
int head;
int tail;
}Queue;
Queue B;
int N,M;
int maze[SIZE][SIZE];
int offset[4][2] = {-1,0,0,1,1,0,0,-1};
int mark[SIZE][SIZE];
int answer;
/***********************************************************************************/
void init_queue(Queue *A)
{
(*A).head=-1;
(*A).tail=-1;
}
int in_queue(Queue *A,Pos val)
{
if( (*A).tail==MAXSIZE-1 )//full
return 0;
(*A).store[ ++(*A).tail]=val;
return 1;
}
int out_queue(Queue *A,Pos * val)
{
if( (*A).tail==-1)//empty
return 0;
*val=(*A).store[++(*A).head];
return 1;
}
int BFS_fast_robot(Pos start, Pos end);
/***********************************************************************************/
int main(void)
{
int tc, T;
int y;
freopen("input.txt", "r", stdin);
// If you remove the statement below, your program's output may not be rocorded
// when your program is terminated after the time limit.
// For safety, please use setbuf(stdout, NULL); statement.
setbuf(stdout, NULL);
scanf("%d", &T);
for(tc=0;tc<T;tc++)
{
int i=0,j=0;
scanf("%d %d",&M,&N); //N-->x, M-->y
scanf("%d %d %d %d",&start.y,&start.x,&end.y,&end.x);
start.change = -1;
start.x=start.x-1;
start.y=start.y-1;
end.x=end.x-1;
end.y=end.y-1;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
{
scanf("%1d",&maze[i][j]);
mark[i][j]=0;
}
answer = MAXSIZE;
answer=BFS_fast_robot(start,end);
if(answer == MAXSIZE)
{
printf("-1
");
}
else
{
printf("%d
",answer);
}
}
return 0;
}
int BFS_fast_robot(Pos start, Pos end)
{
Pos tmp,tmp2;
int k=0,x=0,y=0,tx=0,ty=0,tchange=0;
init_queue(&B);
in_queue(&B,start);
mark[start.x][start.y] = 1;
while(B.head != B.tail && B.tail !=-1)
{
out_queue(&B,&tmp);
if(tmp.x==end.x && tmp.y==end.y)
return tmp.change;
for(k=0;k<4;k++)
{
tx=tmp.x+offset[k][0];
ty=tmp.y+offset[k][1];
tchange=tmp.change+1;
if(tx>=0 && tx<N && ty>=0 && ty<M && mark[tx][ty]==0 )
{
/********************************************************************************/
if(k==0 && maze[tx][ty]==0)//up
{
x=tx;
y=ty;
while(x>=0 && maze[x][y]==0)
{
tmp2.x=x;
tmp2.y=y;
tmp2.change=tchange;
in_queue(&B,tmp2);
mark[x][y]=1;
x--;
}
continue;
}
if(k==1 && maze[tx][ty]==0)//right
{
x=tx;
y=ty;
while(y<M && maze[x][y]==0)
{
tmp2.x=x;
tmp2.y=y;
tmp2.change=tchange;
in_queue(&B,tmp2);
mark[x][y]=1;
y++;
}
continue;
}
if(k==2 && maze[tx][ty]==0)//down
{
x=tx;
y=ty;
while(x<N && maze[x][y]==0)
{
tmp2.x=x;
tmp2.y=y;
tmp2.change=tchange;
in_queue(&B,tmp2);
mark[x][y]=1;
x++;
}
continue;
}
if(k==3 && maze[tx][ty]==0)//left
{
x=tx;
y=ty;
while(y>=0 && maze[x][y]==0)
{
tmp2.x=x;
tmp2.y=y;
tmp2.change=tchange;
in_queue(&B,tmp2);
mark[x][y]=1;
y--;
}
continue;
}
/********************************************************************************/
}
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.