BFS (범위 우선 검색) 간단 한 예제 (2)

이 블 로 그 는 BFS (범위 우선 검색) 문제 에 대한 연습 입 니 다.
색칠 낙 곡 P1162
제목: 숫자 00 으로 구 성 된 방진 에는 임의의 모양 의 폐 합 권 이 있 고 폐 합 권 은 숫자 11 로 구성 되 며 둘 러 쌀 때 상하 좌우 44 개 방향 만 걷는다.현재 폐쇄 권 안의 모든 공간 을 22 로 작성 할 것 을 요구 합 니 다.
문제 풀이: 본 문 제 는 검색 권 내의 1 이 라면 매우 번 거 롭 지만 검색 권 밖의 1 이 라면 그 문장 은 비교적 간단 하 다. 그러나 검색 할 때 권 밖의 모든 점 이 연 결 된 것 이 아니 기 때문에 권 밖의 점 을 폭력 적 으로 검색 할 수 있다. 권 밖의 점 이 고립 되 었 든 아니 든 반드시 네 개의 경계 와 연 결 될 수 있 기 때문에 변 의 범 위 를 옮 겨 다 닐 수 있다.

#include
#include
#include
#include
using namespace std;
#define N 100
struct Node{
       int x, y;
} p, tmp;
queueq;
int vis[N][N];
int dis[N][N];
int dx[4] ={1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n;
void Bfs(int st, int en){
     memset(vis, 0, sizeof(vis));
     p.x = st;
     p.y = en;
     if(dis[st][en] != 1 && dis[st][en] != 3){
     if(dis[st][en] == 0)dis[p.x][p.y] = 3;
     vis[p.x][p.y] = 1;
     q.push(p);
     int cn;
     while(!q.empty()){
        p = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            tmp.x = p.x + dx[i];
            tmp.y = p.y + dy[i];
            if(tmp.x >= 0 && tmp.x < n && tmp.y >= 0 && tmp.y < n && !vis[tmp.x][tmp.y] && !dis[tmp.x][tmp.y]){
               q.push(tmp);
               vis[tmp.x][tmp.y] = 1;
               dis[tmp.x][tmp.y] = 3;
            }
        }

     }
     }
}
int main(){
    while(~scanf("%d", &n)){
        while(!q.empty())q.pop();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cin>>dis[i][j];
            }
        }
        for(int i = 0; i < n; i++){
            Bfs(i, 0);
            Bfs(0, i);//       
            Bfs(n-1, i);
            Bfs(i, n-1);
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(dis[i][j] == 3)
                cout<<0<

Battle City POJ 2312
링크:http://poj.org/problem?id=2312

#include
#include
#include
#include
#include
using namespace std;
#define N 305
struct Node{
       int x, y, step;
       friend bool operator B.step;
       }
}tmp1, tmp2;
int vis[N][N];
char a[N][N];
int n, m, k, flag;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1,-1, 0,  0};
void bfs(int st, int en){
     memset(vis, 0, sizeof(vis));
     vis[st][en] = 1;
     tmp1.x = st;
     tmp1.y = en;
     tmp1.step = 0;
     priority_queueq;
     q.push(tmp1);
     while(!q.empty()){
         tmp1 = q.top();
         q.pop();
         if(a[tmp1.x][tmp1.y] == 'T'){
            flag = 1;
            k = tmp1.step;
            break;
         }
         //cout<=0 && tmp2.x< n&&tmp2.y >= 0&&tmp2.y < m && !vis[tmp2.x][tmp2.y] && a[tmp2.x][tmp2.y] != 'S'&&a[tmp2.x][tmp2.y] != 'R'){
               if(a[tmp2.x][tmp2.y] == 'B'){//          ，   2
                  tmp2.step = tmp1.step+2;
               }
               else{
                 tmp2.step = tmp1.step+1;//       1

               }
               vis[tmp2.x][tmp2.y] = 1;
                  q.push(tmp2);
            }
         }
     }
}
int main(){
    int st, en;
    while(scanf("%d %d", &n, &m) && (m != 0 && n != 0)){
        for(int i = 0; i < n; i++){
            scanf("%s", a[i]);
            for(int j = 0; j < m; j++){
                if(a[i][j] == 'Y'){
                   st = i;
                   en = j;
                }
            }
        }
        flag = 0;
        bfs(st, en);
        if(!flag)cout<

샘물. HRBUST 1143
링크:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1143

#include
#include
#include
#include
#include
using namespace std;
#define N 1005
struct Node {
       int x, y, pre;
}tmp1, tmp2;
int vis[N][N];
int a[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1,-1, 0,  0};
int n, m, step;
void bfs(int st, int en, int pre){
     memset(vis, 0, sizeof(vis));
     vis[st][en] = 1;
     tmp1.x = st;
     tmp1.y = en;
     step = 0;
     tmp1.pre = pre;
     queueq;
     q.push(tmp1);
     while(!q.empty()){
        tmp1 = q.front();
        q.pop();
        //cout< 0 && tmp2.x <= n && tmp2.y > 0 &&tmp2.y <= m && !vis[tmp2.x][tmp2.y] && a[tmp2.x][tmp2.y] <= tmp1.pre){
                vis[tmp2.x][tmp2.y] = 1;
                step++;
                tmp2.pre = tmp1.pre;
                //cout<>a[i][j];
            }
        }
        pre = a[st][en];
        //cout< 
                P1443 
    ：https://www.luogu.org/problemnew/show/P1443 
  #include
#include
#include
#include
#include
using namespace std;
#define N 405
struct Node{
       int x, y;
}tmp1, tmp2;
queueq;
int dx[8] = {1,-1,2,-2,-1,1,2,-2};
int dy[8] = {2,2,1,1,-2,-2,-1,-1};
int vis[N][N];
int dis[N][N];
int n, m;
void Bfs(int st, int en){
     memset(vis, 0, sizeof(vis));
     memset(dis, 0, sizeof(vis));
     tmp1.x = st;
     tmp1.y = en;
     vis[tmp1.x][tmp1.y] = 1;
     q.push(tmp1);
     while(!q.empty()){
        tmp1 = q.front();
        q.pop();
        for(int i = 0; i < 8; i++){
            tmp2.x = tmp1.x + dx[i];
            tmp2.y = tmp1.y + dy[i];
            if(tmp2.x >= 1 && tmp2.x <= n && tmp2.y >= 1 && tmp2.y <= m && !vis[tmp2.x][tmp2.y]){
                q.push(tmp2);
                dis[tmp2.x][tmp2.y] = dis[tmp1.x][tmp1.y] + 1;
                vis[tmp2.x][tmp2.y] = 1;
            }
        }
     }
}
int main(){
    int st, en;
    cin>>n>>m>>st>>en;
    Bfs(st, en);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(dis[i][j] || (i == st && j == en))
            printf("%-5d",dis[i][j]);
            else printf("%-5d", -1);
        }
        cout<
  
Rescue   HDU   1242 
링크:http://acm.hdu.edu.cn/showproblem.php?pid=1242 #include
#include
#include
#include
#include
#define N 205
using namespace std;
struct Node{
       int x, y, val;
       friend bool operator B.val;
       }
}tmp1, tmp2;
priority_queueq;
int dx[]= {-1,0,0,1};
int dy[]= {0,-1,1,0};
int vis[N][N];
char a[N][N];
int n, m, flag, k;
void bfs(int st, int en){
     memset(vis, 0, sizeof(vis));
     vis[st][en] = 1;
     tmp1.x = st;
     tmp1.y = en;
     tmp1.val = 0;
     q.push(tmp1);
     while(!q.empty()){
        tmp1 = q.top();
        q.pop();
        if(a[tmp1.x][tmp1.y] == 'r'){
                k = tmp1.val;
                flag = 1;
                break ;
        }
        // cout<= n || tmp2.x < 0 || tmp2.y < 0 || tmp2.y >= m || vis[tmp2.x][tmp2.y]|| a[tmp2.x][tmp2.y] == '#')
                continue;
            if(a[tmp2.x][tmp2.y] == 'x'){
                tmp2.val = tmp1.val + 2;
                q.push(tmp2);
            }
            else {
                tmp2.val = tmp1.val + 1;
                q.push(tmp2);
            }
            vis[tmp2.x][tmp2.y] = 1;
        }

     }

}
int main(){
    int st, en;
    while(~scanf("%d %d", &n, &m)){
        while(!q.empty())q.pop();
        for(int i = 0; i < n; i++){
            scanf("%s", a[i]);
        }
        flag = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(a[i][j] =='a'){
                    st = i;
                    en = j;
                }
            }
        }
        bfs(st, en);
        if(!flag)cout<

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

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

【Codility Lesson3】FrogJmp

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...

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

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

BFS (범위 우선 검색) 간단 한 예제 (2)

P1443

좋은 웹페이지 즐겨찾기