3개의 댓글이 있습니다.
-
-
universalee -
답변 감사드립니다. 101 넣어도 같은 에러가 뜨네요 ㅠㅠ 아무래도 bfs로는 이 문제가 안풀리는걸까요? 이 문제에 허용되는 메모리가 제법 크던데...
8년 전 link
-
-
-
universalee -
해결했습니다. 다음에 방문해야 할 점의 발견여부를 알려주는 배열을 필요하지 않다고 생각해서 쓰지 않았는데 중복발견되어서 큐에 들어가는 점이 메모리 초과의 원인이 되었던 것 같습니다. 이렇게 쉬운 걸 고민하고 있었네요 ㅜㅜ
8년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
universalee
동적계획법이 아닌 bfs로 풀어봤는데 런타임에러(SIGKILL)가 뜹니다.
메모리초과로 추측된다는데 이 코드에 메모리초과가 날 여지가 있나요?
~~~ c++
#include
#include
#include
#include
using namespace std;
typedef struct _POINT{
int x,y;
}Point;
int n;
int board[100][100];
bool bfs(Point& sp) q;
{
bool ret=false;
queue
q.push(sp);
while(!q.empty())
{
Point p=q.front();
q.pop();
if((p.x==n-1)&&(p.y==n-1))
{
ret=true;
break;
}
Point p1,p2;
p1.x=0,p1.y=0;
p2.x=0,p2.y=0;
int nx1=p.x+board[p.x][p.y],ny1=p.y;
if(nx1<n&&ny1<n)
{
p1.x=nx1,p1.y=ny1;
q.push(p1);
}
int nx2=p.x,ny2=p.y+board[p.x][p.y];
if(nx2<n&&ny2<n)
{
p2.x=nx2,p2.y=ny2;
q.push(p2);
}
}
return ret;
}
int main() {
{
{
int C;
scanf("%d",&C);
while(C!=0)
{
--C;
memset(board,0,sizeof(board));
scanf("%d",&n);
for(int i=0; i
for(int j=0; j
scanf("%d",&board[i][j]);
}
}
Point sp;
sp.x=0,sp.y=0;
if(bfs(sp)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
~~~
8년 전