1034

1034#include#includeusingnamespacestd;#defineDEBUG_IO(0)#defineDEBUG(0)structNode{intx;inty;ints;Node():x(0),y(0),s(0){}};constintN=

#include<stdio.h> 
#include<iostream> 
using namespace std; 
#define DEBUG_IO (0) 
#define DEBUG (0) 
  
struct Node 
{ 
    int x;  
    int y; 
    int s; 
    Node():x(0),y(0),s(0) 
    { 
    } 
}; 
  
const int N = 1001; 
const int dis[4][2] = {
  
  {1, 0},{0, 1},{-1, 0},{0, -1}}; 
  
const int MAXQ = 100000; 
Node Q0[MAXQ]; 
Node Q1[MAXQ]; 
char map[N][N]; 
bool vis[N][N]; 
int front0 = 0; 
int rear0 = 1; 
int front1 = 0; 
int rear1 = 0; 
int x = 0; 
int y = 0; 
int s = 0; 
int n; 
bool isOver = false; 
  
void bfs0(); 
void bfs1(); 
  
int main() 
{ 
#if DEBUG  
    freopen("input.txt", "r", stdin);  
    setbuf(stdout, NULL);  
#endif 
    int i, j, k; 
    scanf("%d", &n); 
  
    for(i = 0; i < n; i++) 
    { 
        for(j = 0; j < n; j++) 
        { 
            scanf("%d", &map[i][j]); 
            vis[i][j] = 0; 
        } 
    } 
    isOver = false; 
    vis[0][0] = 1; 
    while(front0 != rear0 || front1 != rear1) 
    { 
        if(isOver) 
        { 
            break; 
        } 
        if(front0 != rear0) 
        { 
            bfs0(); 
        } 
        else if(front1 != rear1) 
        { 
            bfs1(); 
        } 
    } 
    printf("%d", Q0[front0].s); 
    return 0; 
} 
  
void bfs0() 
{ 
            x = Q0[front0].x; 
            y = Q0[front0].y; 
            s = Q0[front0].s; 
#if DEBUG_IO  
            cout <<"De Q0:"<<"("<<x<<","<<y<<","<<s<<") "; 
#endif 
            if(x == n-1 && y == n-1) 
            { 
                isOver = true; 
                return; 
            } 
            for(int i = 0; i < 4; i++) 
            { 
                x += dis[i][0]; 
                y += dis[i][1]; 
                if(x >= 0 && x < n && y >=0 && y < n && vis[x][y] == 0) 
                { 
                    vis[x][y] = 1; 
                    if(map[x][y] == 0) 
                    { 
                        //vis[x][y] = 1; 
                        Q0[rear0].x = x; 
                        Q0[rear0].y = y; 
                        Q0[rear0].s = s; 
#if DEBUG_IO  
                        cout <<"En Q0:"<<"("<<x<<","<<y<<","<<s<<") "; 
#endif 
                        rear0++; 
                        rear0=(rear0)%MAXQ; 
                    } 
                    else
                    { 
                        Q1[rear1].x = x; 
                        Q1[rear1].y = y; 
                        Q1[rear1].s = s + 1; 
#if DEBUG_IO  
                        cout <<"En Q1:"<<"("<<x<<","<<y<<","<<s + 1<<") "; 
#endif 
                        rear1++; 
                        rear1=(rear1)%MAXQ; 
                    } 
                } 
                x -= dis[i][0]; 
                y -= dis[i][1]; 
            } 
            front0++; 
            front0=(front0)%MAXQ; 
#if DEBUG_IO 
            cout<<endl; 
#endif 
} 
  
void bfs1() 
{ 
            x = Q1[front1].x; 
            y = Q1[front1].y; 
            s = Q1[front1].s; 
#if DEBUG_IO  
            cout <<"De Q1:"<<"("<<x<<","<<y<<","<<s<<") "; 
#endif 
            if(x == n-1 && y == n-1) 
            { 
                isOver = true; 
                return; 
            } 
            for(int i = 0; i < 4; i++) 
            { 
                x += dis[i][0]; 
                y += dis[i][1]; 
                if(x >= 0 && x < n && y >=0 && y < n && vis[x][y] == 0) 
                { 
                    vis[x][y] = 1; 
                    if(map[x][y] == 1) 
                    { 
                        Q1[rear1].x = x; 
                        Q1[rear1].y = y; 
                        Q1[rear1].s = s + 1; 
#if DEBUG_IO  
                        cout <<"En Q1:"<<"("<<x<<","<<y<<","<<s+1<<") "; 
#endif 
                        rear1++; 
                        rear1=(rear1)%MAXQ; 
                    } 
                    else
                    { 
                        Q0[rear0].x = x; 
                        Q0[rear0].y = y; 
                        Q0[rear0].s = s; 
#if DEBUG_IO  
                        cout <<"En Q0:"<<"("<<x<<","<<y<<","<<s<<") "; 
#endif 
                        rear0++; 
                        rear0=(rear0)%MAXQ; 
                    } 
                } 
                x -= dis[i][0]; 
                y -= dis[i][1]; 
            } 
            front1++; 
            front1=(front1)%MAXQ; 
#if DEBUG_IO 
            cout<<endl; 
#endif 
  
} 
/************************************************************** 
    Problem: 1034 
    User: ddddd 
    Language: C++ 
    Result: 正确 
    Time:320 ms 
    Memory:4792 kb 
****************************************************************/

今天的文章1034分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/4563.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注