misschuer

常用链接

统计

积分与排名

百事通

最新评论

hdu 1175 连连看

#include <iostream>
#define MAXN 1001
#include 
<queue>
using namespace std;

int mat[MAXN][MAXN];
int mark[MAXN][MAXN];
int n, m, sx, sy, ex, ey, q;
//int mov[ 4 ][ 2 ] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
//搜索的顺序影响结果
int mov[ 4 ][ 2 ] = {{01}, {10}, {0-1}, {-10}};

struct Node {
    
    
int x;
    
int y;
    
int turn;
    
int dir;
};

void BFS() {
     
    queue
<Node> Q;
    Node p, q;
    p.x 
= sx;   p.y = sy;
    mark[ sx ][ sy ] 
= 0;
    p.dir 
= -1; p.turn = 0;

    Q.push(p);
    
    
while(!Q.empty()) {
        
        q 
= Q.front();
        Q.pop();

        
if(q.x == ex && q.y == ey) {
            
            puts(
"YES");
            
return ;
        }
        
        
//0下, 1上, 2左, 3右
        for(int i = 0; i < 4++ i) {
        
            p.x 
= q.x + mov[ i ][ 0 ];
            p.y 
= q.y + mov[ i ][ 1 ];
            p.turn 
= q.turn;
            p.dir 
= q.dir;
            
            
if(q.dir == -1) {
               
                p.dir 
= i;
                p.turn 
= 0;
            }
            
else if(q.dir != i) {
                
                p.turn 
++;
                p.dir 
= i;
            }


            
if(p.x < 1 || p.x > n || p.y < 1 || p.y > m) continue;

            
if(mat[ p.x ][ p.y ] && !(p.x == ex && p.y == ey) || p.turn > 2continue;
            


            
if(mark[ p.x ][ p.y ] > p.turn) {
    
                mark[ p.x ][ p.y ] 
= p.turn;
                Q.push(p);
            }
        }
    }
    
    puts(
"NO");
}

void res() {
    
    
    scanf(
"%d"&q);
    
while(q --) {
        
        scanf(
"%d %d %d %d"&sx, &sy, &ex, &ey);
        
if(sx == ex && sy == ey) {
        
            puts(
"NO");
            
continue;
        }

        
if(mat[ sx ][ sy ] != mat[ ex ][ ey ] || mat[ sx ][ sy ] == 0 || mat[ ex ][ ey ] == 0) {
        
            puts(
"NO");
            
continue;
        }

        
for(int i = 1; i <= n; ++ i) {
        
            
for(int j = 1; j <= m; ++ j) {
            
                mark[ i ][ j ] 
= 10000000;
            }
        }

        BFS();
    }
}

int main() {
    
    
    
while(~scanf("%d %d"&n, &m)) {
        
        
if(n == 0 && m == 0break;
        
        
for(int i = 1; i <= n; ++ i) {
            
            
for(int j = 1; j <= m; ++ j) {
                
                scanf(
"%d"&mat[ i ][ j ]);
            }
        }
        res();
    }
    
return 0;
}

posted on 2011-03-17 12:16 此最相思 阅读(788) 评论(4)  编辑 收藏 引用

评论

# re: hdu 1175 连连看[未登录] 2011-05-06 20:59 Xy

你的代码WA的
  回复  更多评论   

# re: hdu 1175 连连看 2011-07-21 11:03 ahfywff

你的代码有一点小问题,下面这组测试数据的结果应该是“YES”

3 4
1 0 0 2
0 0 0 0
2 2 2 1
1
1 1 3 4

代码中的 if(mark[ p.x ][ p.y ] > p.turn) 应该改为 if(mark[ p.x ][ p.y ] >= p.turn)  回复  更多评论   

# re: hdu 1175 连连看 2011-08-13 14:50 misschuer

@Xy
我表示刚看到 然后测试了一下 可以过的吧
  回复  更多评论   

# re: hdu 1175 连连看 2011-08-13 14:54 misschuer

由于HDU的数据不强所以 代码是有点错误  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理