诡异的楼梯 BFS hdu 1180

雨点打透心脏的1/2处 2021-11-02 14:32 217阅读 0赞

这题好邪恶啊。做了两个半小时wa得好辛苦。

原因是。。可以停留在空格里的。题意不清啊。

还有就是注意标记。。开了个三维的数组。。分奇数步和偶数步标记。。

最后有可能时间多的先出队。所以要选个最小的时间。。

其实可以用优先队列做。。

艾。。这代码有点太长了。。

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <deque>
    #include <algorithm>
    #include <iostream>
    
    using namespace std;
    
    int a, b, c, d, N, M, t;
    char map[50][50];
    
    
    
    int hash[3][50][50];
    
    struct node
    {
         
    int x, y, t; 
    }NODE;
    
    int judge( int x, int y)
    {
         
    if (x < 1 || x > N || y < 1|| y > M)
    return 0;
    return 1;
    }
    
    
    void BFS(  )
    {
         
    int i, j, x1, x2, y1, y2, t2, t1;
        deque<node>q;
        memset(hash, 0, sizeof(hash));
        NODE.x = a, NODE.y = b, NODE.t = 0;
    //map[a][b]='*';
        hash[0][a][b]=1;
        t = 0x7f7f7f7f;
        q.push_back(NODE);
    while (!q.empty( ))
        {
         
            NODE = q.front( );
            q.pop_front( );
            x1 = NODE.x, y1 = NODE.y, t1 = NODE.t;
    //printf("(%d,%d)->%d\n",x1,y1,t1);
            if (x1 == c && y1 == d ) {
         
    if (t1 < t)
                t = t1;
            }
    //向右移动 
            x2 = x1 + 0, y2 = y1  + 1, t2 = t1 + 1, NODE.t = 0;
            NODE.x = x2, NODE. y = y2, NODE.t = t2;
    if ( judge(x2, y2) && map[x2][y2] != '*' && map[x2][y2] != '-' && map[x2][y2] !='|' && !hash[t2 % 2][x2][y2]) {
         
                hash[t2%2][x2][y2] = 1;
                q.push_back(NODE);
            }
    else if ( (map[x2][y2] == '-' && t1 % 2 == 0 )|| (map[x2][y2] == '|' && t1 % 2 == 1)) {
         
    //NODE.t;
                NODE.y+=1;
                y2 += 1;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push_back(NODE);
                }
            }
    else if  (map[x2][y2] == '-' || map[x2][y2] == '|') {
         
    //NODE.t;
                NODE.y+=1;
                y2 += 1;
                NODE.t++;
                t2++;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push_back(NODE);
                }
            }
    //向左移动 
            x2 = x1 + 0, y2 = y1  - 1, t2 = t1 + 1, NODE.t = 0;
            NODE.x = x2, NODE. y = y2, NODE.t = t2;            
    if ( judge(x2, y2) && map[x2][y2] != '*' && map[x2][y2] != '-' && map[x2][y2] !='|' && !hash[t2%2][x2][y2]) {
         
    //map[x2][y2] = '*';
                hash[t2%2][x2][y2] = 1;
                q.push_back(NODE);
            }
    else if ( (map[x2][y2] == '-' && t1 % 2 == 0 )|| (map[x2][y2] == '|' && t1 % 2 == 1) && !hash[t2%2][x2][y2]) {
         
    //NODE.t++;
                NODE.y-=1;
                y2 -= 1;
    if( judge(x2, y2) && map[x2][y2] != '*')
                {   //map[x2][y2]='*';
                    hash[t2%2][x2][y2] = 1;
                    q.push_back(NODE);
                }
            }
    else if  (map[x2][y2] == '-' || map[x2][y2] == '|') {
         
    //NODE.t;
                NODE.y-=1;
                y2 -= 1;
                NODE.t++;
                t2++;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push_back(NODE);
                }
            }
    //向上移动 
                x2 = x1 - 1, y2 = y1 , t2 = t1 + 1, NODE.t = 0;
                NODE.x = x2, NODE. y = y2, NODE.t = t2;            
    if ( judge(x2, y2) && map[x2][y2] != '*' && map[x2][y2] != '-' && map[x2][y2] !='|' && !hash[t2%2][x2][y2]) {
         
    //map[x2][y2] = '*';
                hash[t2%2][x2][y2] = 1;
                q.push_back(NODE);
            }
    else if ( (map[x2][y2] == '-' && t1 % 2 == 1 )|| (map[x2][y2] == '|' && t1 % 2 == 0)&& !hash[t2%2][x2][y2]) {
         
    //NODE.t++;
                NODE.x-=1;
                x2 -= 1;
    if( judge(x2, y2) && map[x2][y2] != '*')
                    {   
    //map[x2][y2]='*';
                        hash[t2%2][x2][y2] = 1;
                        q.push_back(NODE);
                    }
            }
    else if  (map[x2][y2] == '-' || map[x2][y2] == '|') {
         
                NODE.x-=1;
                x2 -= 1;
                NODE.t++;
                t2++;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push_back(NODE);
                }
            }
    //向下移动 
                x2 = x1 + 1, y2 = y1 , t2 = t1 + 1, NODE.t = 0;
            NODE.x = x2, NODE. y = y2, NODE.t = t2;            
    if ( judge(x2, y2) && map[x2][y2] != '*' && map[x2][y2] != '-' && map[x2][y2] !='|' && !hash[t2%2][x2][y2]) {
         
    
                hash[t2%2][x2][y2] = 1;
                q.push_back(NODE);
            }
    else if ( (map[x2][y2] == '-' && t1 % 2 == 1 )|| (map[x2][y2] == '|' && t1 % 2 == 0)&& !hash[t2%2][x2][y2]) {
         
                NODE.x += 1;
                x2 += 1;
    if( judge(x2, y2) && map[x2][y2] != '*')
                    {  
                       hash[t2%2][x2][y2] = 1;
                       q.push_back(NODE);
                    }
    
            }
    else if  (map[x2][y2] == '-' || map[x2][y2] == '|') {
         
                NODE.x+=1;
                x2 += 1;
                NODE.t++;
                t2++;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push_back(NODE);
                }
            }
        }     
    }
    int main( )
    {
         
    
    int i, j;
    
    while (scanf("%d%d", &N, &M) != EOF)
        {
         
    for (i = 1; i <= N; i++)
    for( j = 1; j <= M; j++) {
         
                     cin>>map[i][j];
    if (map[i][j] == 'S')
                     {
         
                        a = i;
                        b = j;
                    }
    if (map[i][j] == 'T')
                    {
         
                        c = i;
                        d = j;
                    }
                }
    
            BFS( );
            printf("%d\n",t);
        }
    return 0;
    }

用优先队列。。。

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <deque>
    #include <algorithm>
    #include <iostream>
    #include <queue>
    
    using namespace std;
    
    int a, b, c, d, N, M, t;
    char map[50][50];
    
    
    
    int hash[3][50][50];
    
    struct node
    {
         
    int x, y, t;
    bool operator < (const node &A) const
        {
         
    return A.t < t;
        }
    }NODE;
    
    
    
    
    int judge( int x, int y)
    {
         
    if (x < 1 || x > N || y < 1|| y > M)
    return 0;
    return 1;
    }
    
    
    void BFS(  )
    {
         
    int i, j, x1, x2, y1, y2, t2, t1;
        priority_queue<node>q; //优先队列 
        memset(hash, 0, sizeof(hash));
        NODE.x = a, NODE.y = b, NODE.t = 0;
    //map[a][b]='*';
        hash[0][a][b]=1;
        t = 0x7f7f7f7f;
        q.push(NODE);
    while (!q.empty( ))
        {
         
            NODE = q.top( );
            q.pop( );
            x1 = NODE.x, y1 = NODE.y, t1 = NODE.t;
    //printf("(%d,%d)->%d\n",x1,y1,t1);
            if (x1 == c && y1 == d ) {
         
                t = t1;
    break;
            }
    //向右移动 
            x2 = x1 + 0, y2 = y1  + 1, t2 = t1 + 1, NODE.t = 0;
            NODE.x = x2, NODE. y = y2, NODE.t = t2;
    if ( judge(x2, y2) && map[x2][y2] != '*' && map[x2][y2] != '-' && map[x2][y2] !='|' && !hash[t2 % 2][x2][y2]) {
         
                hash[t2%2][x2][y2] = 1;
                q.push(NODE);
            }
    else if ( (map[x2][y2] == '-' && t1 % 2 == 0 )|| (map[x2][y2] == '|' && t1 % 2 == 1)) {
         
    //NODE.t;
                NODE.y+=1;
                y2 += 1;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push(NODE);
                }
            }
    else if  (map[x2][y2] == '-' || map[x2][y2] == '|') {
         
    //NODE.t;
                NODE.y+=1;
                y2 += 1;
                NODE.t++;
                t2++;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push(NODE);
                }
            }
    //向左移动 
            x2 = x1 + 0, y2 = y1  - 1, t2 = t1 + 1, NODE.t = 0;
            NODE.x = x2, NODE. y = y2, NODE.t = t2;            
    if ( judge(x2, y2) && map[x2][y2] != '*' && map[x2][y2] != '-' && map[x2][y2] !='|' && !hash[t2%2][x2][y2]) {
         
    //map[x2][y2] = '*';
                hash[t2%2][x2][y2] = 1;
                q.push(NODE);
            }
    else if ( (map[x2][y2] == '-' && t1 % 2 == 0 )|| (map[x2][y2] == '|' && t1 % 2 == 1) && !hash[t2%2][x2][y2]) {
         
    //NODE.t++;
                NODE.y-=1;
                y2 -= 1;
    if( judge(x2, y2) && map[x2][y2] != '*')
                {   //map[x2][y2]='*';
                    hash[t2%2][x2][y2] = 1;
                    q.push(NODE);
                }
            }
    else if  (map[x2][y2] == '-' || map[x2][y2] == '|') {
         
    //NODE.t;
                NODE.y-=1;
                y2 -= 1;
                NODE.t++;
                t2++;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push(NODE);
                }
            }
    //向上移动 
                x2 = x1 - 1, y2 = y1 , t2 = t1 + 1, NODE.t = 0;
                NODE.x = x2, NODE. y = y2, NODE.t = t2;            
    if ( judge(x2, y2) && map[x2][y2] != '*' && map[x2][y2] != '-' && map[x2][y2] !='|' && !hash[t2%2][x2][y2]) {
         
    //map[x2][y2] = '*';
                hash[t2%2][x2][y2] = 1;
                q.push(NODE);
            }
    else if ( (map[x2][y2] == '-' && t1 % 2 == 1 )|| (map[x2][y2] == '|' && t1 % 2 == 0)&& !hash[t2%2][x2][y2]) {
         
    //NODE.t++;
                NODE.x-=1;
                x2 -= 1;
    if( judge(x2, y2) && map[x2][y2] != '*')
                    {   
    //map[x2][y2]='*';
                        hash[t2%2][x2][y2] = 1;
                        q.push(NODE);
                    }
            }
    else if  (map[x2][y2] == '-' || map[x2][y2] == '|') {
         
                NODE.x-=1;
                x2 -= 1;
                NODE.t++;
                t2++;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push(NODE);
                }
            }
    //向下移动 
                x2 = x1 + 1, y2 = y1 , t2 = t1 + 1, NODE.t = 0;
            NODE.x = x2, NODE. y = y2, NODE.t = t2;            
    if ( judge(x2, y2) && map[x2][y2] != '*' && map[x2][y2] != '-' && map[x2][y2] !='|' && !hash[t2%2][x2][y2]) {
         
    
                hash[t2%2][x2][y2] = 1;
                q.push(NODE);
            }
    else if ( (map[x2][y2] == '-' && t1 % 2 == 1 )|| (map[x2][y2] == '|' && t1 % 2 == 0)&& !hash[t2%2][x2][y2]) {
         
                NODE.x += 1;
                x2 += 1;
    if( judge(x2, y2) && map[x2][y2] != '*')
                    {  
                       hash[t2%2][x2][y2] = 1;
                       q.push(NODE);
                    }
    
            }
    else if  (map[x2][y2] == '-' || map[x2][y2] == '|') {
         
                NODE.x+=1;
                x2 += 1;
                NODE.t++;
                t2++;
    if( judge(x2, y2) && map[x2][y2] != '*' && !hash[t2%2][x2][y2])
                {   
                    hash[t2%2][x2][y2] = 1;
                    q.push(NODE);
                }
            }
        }     
    }
    int main( )
    {
         
    
    int i, j;
    
    while (scanf("%d%d", &N, &M) != EOF)
        {
         
    for (i = 1; i <= N; i++)
    for( j = 1; j <= M; j++) {
         
                     cin>>map[i][j];
    if (map[i][j] == 'S')
                     {
         
                        a = i;
                        b = j;
                    }
    if (map[i][j] == 'T')
                    {
         
                        c = i;
                        d = j;
                    }
                }
    
            BFS( );
            printf("%d\n",t);
        }
    return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2011/08/09/2131978.html