coj1188_bfs.cpp

这是浙大acm,北大acm上,还有地大acm上的题解,全部是关于搜索算法的,题目文件名上有

#include <stdio.h> 
#include <string.h> 
int z[1001][1001]; 
int mark[1001][1001]; 
int n; 
int dir[8][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}}; 
int q[1000005][3]; 
     
int bfs() 
{ 
    int front, rear; 
    int i, j, tx , ty; 
    q[0][0] = 0; q[0][1] = 0; q[0][2] = 0; 
    mark[0][0] = 1; 
    front = -1; rear = 1; 
    while(front != rear) { 
        front++; 
        tx = q[front][0]; 
        ty = q[front][1]; 
        for(i = 0; i < 8; i++) { 
            int x = tx + dir[i][0]; 
            int y = ty + dir[i][1]; 
            if(x < 0 || x >= n || y < 0 || y >= n || mark[x][y] || !z[x][y]) continue; 
            mark[x][y] = 1; 
            q[rear][0] = x;  
            q[rear][1] = y; 
            q[rear][2] = q[front][2]+1; 
            if(x == n-1 && y == n-1) return q[rear][2]; 
            rear++; 
        } 
    } 
    return -1; 
}     
int main() 
{ 
    int i,j,k,x,y; 
    while(EOF!=scanf("%d",&n) && n) 
    { 
        if(n==0)break; 
        for(i=0;i<n;i++) 
        for(j=0;j<n;j++) 
        scanf("%d",&z[i][j]); 
        memset(mark, 0, sizeof(mark)); 
        x=0; 
        y=0; 
        int tmp = bfs(); 
        if(tmp == -1) printf("IMPOSSIBLE\n"); 
        else printf("%d\n", tmp); 
    }   
    return 0;   
}