HDU 1728번 미로 탈출
이 문제는 처음에 간단한 검색문제인 줄 알았는데 여러 번 틀렸다. 인터넷에서 참고를 하고 나서야 문득 깨달았다. 한 방향을 끝까지 계속 검색하거나 몇 점을 다시 팀에 들여보내 다시 검색을 하게 했다. 이렇게 다 쓴 후에도wa가 되었다. 코드를 다시 한 번 보고 한 글자를 잘못 썼다.
참조 코드:
#include<stdio.h>
#include<queue>
using namespace std;
int n,m,k;
char s[105][105];
int vis[105][105],dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
struct zhang
{
int x,y,bu,d;
};
bool diy(int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='.')
return true ;
else return false ;
}
void bfs(int x1,int y1)
{
int i;
queue<zhang>q;
zhang current,next;
for(i=0;i<4;i++)
{
current.x=x1+dx[i];
current.y=y1+dy[i];
current.bu=0;
current.d=i;
if(diy(current.x,current.y))
{
vis[current.x][current.y]=0;
q.push(current);
}
}
while(!q.empty())
{
current=q.front();
q.pop();
for(i=0;i<4;i++)
{
next.x=current.x+dx[i];
next.y=current.y+dy[i];
if(current.d!=i)
next.bu=current.bu+1;
else next.bu=current.bu;
next.d=i;
if(next.bu<=k&&diy(next.x,next.y))
{
if(next.bu<=vis[next.x][next.y])// ！ ，
{ //
vis[next.x][next.y]=next.bu;
q.push(next);
}
}
}
}
}
int main()
{
int T,i,y1,x1,x2,y2;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%s",s[i]);
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
y1--;x1--;y2--;x2--;
for(i=0;i<n;i++)
for(int j=0;j<m;j++)
vis[i][j]=20;
bfs(x1,y1);
if(vis[x2][y2]<=k)
printf("yes
");
else printf("no
");
}
return 0 ;
}
소스 코드:
#include<stdio.h>
#include<queue>
using namespace std;
int vis[150][150];
char s[150][150];
int n,m,k,y2,x2;
struct zhang
{
int x,y,bu,d;
};
void bfs(int x1,int y1)
{
int i;
zhang current,next;
queue<zhang>q;
current.x=x1;
current.y=y1;
current.bu=0;
current.d=-1;
vis[current.x][current.y]=-1;
q.push(current);
while(!q.empty())
{
current=q.front();
q.pop();
if(current.d==-1)//
{
for(i=current.y+1;i<m;i++)// 1
if(s[current.x][i]!='*')
{
next.d=1;
next.x=current.x;
next.y=i;
next.bu=0;
vis[next.x][next.y]=0;
q.push(next);
}
else break;
for(i=current.y-1;i>=0;i--)// 2
if(s[current.x][i]!='*')
{
next.d=2;
next.x=current.x;
next.y=i;
next.bu=0;
vis[next.x][next.y]=0;
q.push(next);
}
else break;
for(i=current.x-1;i>=0;i--)// 3
if(s[i][current.y]!='*')
{
next.d=3;
next.y=current.y;
next.x=i;
next.bu=0;
vis[next.x][next.y]=0;
q.push(next);
}
else break;
for(i=current.y+1;i<n;i++)// 4
if(s[i][current.y]!='*')
{
next.d=4;
next.y=current.y;
next.x=i;
next.bu=0;
vis[next.x][next.y]=0;
q.push(next);
}
else break;
}
else {//
for(i=current.y+1;i<m;i++)// 1
if(s[current.x][i]!='*')
{
if(current.d!=1)
next.bu=current.bu+1;
else
next.bu=current.bu;
if(next.bu<vis[current.x][i])
{
vis[current.x][i]=next.bu;
next.d=1;
next.x=current.x;
next.y=i;
q.push(next);
}
}
else break;
for(i=current.y-1;i>=0;i--)// 2
if(s[current.x][i]!='*')
{
if(current.d!=2)
next.bu=current.bu+1;
else
next.bu=current.bu;
if(next.bu<vis[current.x][i])
{
vis[current.x][i]=next.bu;
next.d=2;
next.x=current.x;
next.y=i;
q.push(next);
}
}
else break;
for(i=current.x-1;i>=0;i--)// 3
if(s[i][current.y]!='*')
{
if(current.d!=3)
next.bu=current.bu+1;
else
next.bu=current.bu;
if(next.bu<vis[i][current.y])
{
vis[i][current.y]=next.bu;
next.d=3;
next.x=i;
next.y=current.y;
q.push(next);
}
}
else break;
for(i=current.x+1;i<n;i++)// 4
if(s[i][current.y]!='*')
{
if(current.d!=4)
next.bu=current.bu+1;
else
next.bu=current.bu;
if(next.bu<vis[i][current.y])
{
vis[i][current.y]=next.bu;
next.d=4;
next.x=i;
next.y=current.y;
q.push(next);
}
}
else break;
}
}
}
int main()
{
int T,x1,y1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",s[i]);
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
y2--; x2--;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
vis[i][j]=20;
bfs(x1-1,y1-1);
if(vis[x2][y2]<=k)
printf("yes
");
else
printf("no
");
}
return 0;
}
//
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
