西北工大算法程序集锦

#include<stdio.h> void readdata(); void init(); int search(); int emptyopen(); int takeoutofopen(); int canmoveto(int,int,int*,int*,int); int isaim(int row, int col); int used(int,int); void addtoopen(int,int); int a[12][12]; int open[20],head,tail,openlen=20; int s,t; int main() { int number; readdata(); init(); number=search(); printf("%d\n",number); } int search() { int u, row, col, r, c, i, num; while(!emptyopen()) { u=takeoutofopen(); row=u/12; col=u%12; num=a[row][col]; for(i=0;i<4;i++) { if(canmoveto(row,col,&r,&c,i)) { if(isaim(r,c)) return(num+1); if(!used(r,c)) { a[r][c]=num+1; addtoopen(r,c); } } } } } int emptyopen() { if(head==tail) return(1); else return(0); } int takeoutofopen() { int u; if(head==tail) { return(-1); } u=open[head++]; head=head%openlen; return(u); } int canmoveto(int row, int col, int *p, int *q, int direction) { int r,c; r=row; c=col; switch(direction) { case 0: c--; break; case 1: r++; break; case 2: c++; break; case 3: r--; } *p=r; *q=c; if(r<0||r>=12||c<0||c>=12) return(0); if(a[r][c]==0) return(1); return(0); } int isaim(int row, int col) { if(row*12+col==t) return(1); else return(0); } int used(int row, int col) { if(a[row][col]==0) return(0); else return(1); } void addtoopen(int row, int col) { int u; u=row*12+col; open[tail++]= u; tail=tail%openlen; } void readdata() { int i,j,row,col; char str[20]; // scanf("%d",&n); scanf("%d%d",&row,&col); s=(row-1)*12+col-1; scanf("%d%d",&row,&col); t=(row-1)*12+col-1; gets(str); for(i=0;i<12;i++) { gets(str); for(j=0;j<12;j++) if(str[j]=='.') a[i][j]=0; else a[i][j]=-2; } } void init() { head=0; tail=1; open[0]=s; }