HEU1728 미로 탈출

제목 주소: 클릭하여 링크 열기
사고: DFS로 시간을 초과하기 쉬우므로 BFS로 한 방향으로 끝까지 검색하고 가지를 많이 줄여야 한다.
시간 초과 코드:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;


int visit[110][110];
char map[110][110];
int m,n,endi,endj,flag,k;
int dir[4][2] = {{-1,0,},{1,0},{0,-1},{0,1}};


void dfs(int x,int y,int direction,int sum)
{
    int i,newx,newy;
    if(flag)
        return;
    if(sum > k)
        return;
    if(x == endi && y == endj)
    {
        flag = 1;
        return;
    }
    for(i=0; i<4; i++)
    {
        newx = x + dir[i][0];
        newy = y + dir[i][1];
        if(newx > 0 && newy > 0 && newx <= m && newy <= n && map[newx][newy] != '*' && !visit[newx][newy])
        {
            visit[newx][newy] = 1;
            if(direction == i)
                dfs(newx,newy,i,sum);
            else
                dfs(newx,newy,i,sum+1);
            visit[newx][newy] = 0;
        }
    }
}
int main()
{
    int t,i,j,x1,y1;
    cin>>t;
    while(t--)
    {
        memset(visit,0,sizeof(visit));
        flag = 0;
        cin>>m>>n;
        for(i=1; i<=m; i++)
        {
            for(j=1; j<=n; j++)
            {
                cin>>map[i][j];
            }
        }
        cin>>k>>y1>>x1>>endj>>endi;
        for(i=0; i<4; i++)
        {
            dfs(x1,y1,i,0);
        }
        if(flag)
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}

DFS가 DFS초로 지나간 것을 보았습니다. 너무 잘 줄였습니다. 아이디어를 쓰세요. DFS는visit수 그룹 표시를 사용하지 않아도 됩니다. 맵을 다시 거슬러 올라가기만 하면 됩니다. 감가는 주로
오류 코드:

#include<iostream>
#include<queue>

using namespace std;

char map[110][110];
int dir[4][2] = {{-1,0,},{1,0},{0,-1},{0,1}};
int m,n,k,endi,endj;

struct node
{
    int x;
    int y;
    int dir;
}a[10010];
bool check(int x,int y)
{
    if(x>0 && y>0 && x<=m && y<=n && map[x][y] != '*')
        return true;
    return false;
}
void bfs(int x,int y)
{
    if(x == endi && y == endj)
    {
        cout<<"yes"<<endl;
        return;
    }
    int i,newx,newy;
    queue<node> q;
    node in,out;
    in.x = x;
    in.y = y;
    in.dir = -1;
    q.push(in);
    while(!q.empty())
    {
        out = q.front();
        q.pop();
        for(i=0; i<4; i++)
        {
            newx = out.x + dir[i][0];
            newy = out.y + dir[i][1];
            while(check(newx,newy))
            {
                in.x = newx;
                in.y = newy;
                in.dir = out.dir + 1;
                q.push(in);
                map[newx][newy] = '*';//           ，   ，          
                if(newx == endi && newy == endj && in.dir <= k)
                {
                    cout<<"yes"<<endl;
                    return;
                }
                newx += dir[i][0];
                newy += dir[i][1];
            }
        }
    }
    cout<<"no"<<endl;
}
int main()
{
    int t,i,j,x1,y1;
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        for(i=1; i<=m; i++)
        {
            for(j=1; j<=n; j++)
            {
                cin>>map[i][j];
            }
        }
        cin>>k>>y1>>x1>>endj>>endi;
        bfs(x1,y1);
    }
    return 0;
}

AC 코드:

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int visit[110][110];
char map[110][110];
int dir[4][2] = {{-1,0,},{1,0},{0,-1},{0,1}};
int m,n,k,endi,endj;

struct node
{
    int x;
    int y;
    int dir;
}a[10010];
bool check(int x,int y)
{
    if(x>0 && y>0 && x<=m && y<=n && map[x][y] != '*')
        return true;
    return false;
}
void bfs(int x,int y)
{
    if(x == endi && y == endj)
    {
        cout<<"yes"<<endl;
        return;
    }
    int i,newx,newy;
    queue<node> q;
    node in,out;
    in.x = x;
    in.y = y;
    in.dir = -1;
    q.push(in);
    while(!q.empty())
    {
        out = q.front();
        q.pop();
        for(i=0; i<4; i++)
        {
            newx = out.x + dir[i][0];
            newy = out.y + dir[i][1];
            while(check(newx,newy))
            {
                if(!visit[newx][newy])
                {
                    in.x = newx;
                    in.y = newy;
                    in.dir = out.dir + 1;
                    q.push(in);
                    visit[newx][newy] = 1;
                    if(newx == endi && newy == endj && in.dir <= k)
                    {
                        cout<<"yes"<<endl;
                        return;
                    }
                }
                newx += dir[i][0];
                newy += dir[i][1];
            }
        }
    }
    cout<<"no"<<endl;
}
int main()
{
    int t,i,j,x1,y1;
    cin>>t;
    while(t--)
    {
        memset(visit,0,sizeof(visit));
        cin>>m>>n;
        for(i=1; i<=m; i++)
        {
            for(j=1; j<=n; j++)
            {
                cin>>map[i][j];
            }
        }
        cin>>k>>y1>>x1>>endj>>endi;
        bfs(x1,y1);
    }
    return 0;
}

대신풀이 주소: 클릭하여 링크 열기

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HEU1728 미로 탈출

좋은 웹페이지 즐겨찾기