usaco_maze1.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROG: maze1
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <cstring>
#include <memory>
#include <queue>
using namespace std;
ifstream fin("maze1.in");
ofstream fout("maze1.out");
struct Node{
       int x,y;
       int step;};
struct Tnode{
       unsigned sit;
       int step1,step2;
       };
int main()
{
    Tnode a[100][38];
    char ch;
    Node door1,door2,now;
    int i,j,max=0,min,m,n;
    bool flag=true;
    queue<Node> q;
    fin>>n>>m;
    fin.get();
    for(i=0;i<m;i++)
            for(j=0;j<n;j++)
            {a[i][j].sit=0;a[i][j].step1=-1;a[i][j].step2=-1;}
    for(i=0;i<2*m+1;i++){
       for(j=0;j<2*n+1;j++)
       {
           ch=fin.get();
           if((i==0 && ch == ' ') || (i==2*m && ch == ' ') || (j==0 && ch ==' ') || (j==2*n && ch ==' '))
             if(flag) {door1.x=(i-1)/2;door1.y=(j-1)/2;flag=false; door1.step=1;}
             else {door2.x=(i-1)/2;door2.y=(j-1)/2;door2.step=1;}
           if(i%2==0)
           {
               if(ch=='-') 
               {if(i<2*m) a[(i+1)/2][(j-1)/2].sit+=1;  if(i>0) a[(i-1)/2][(j-1)/2].sit+=4;}
               
           }
           else if(ch == '|') 
           {
                if(j>0) a[(i-1)/2][(j-1)/2].sit+=2;
                if(j<2*n) a[(i-1)/2][(j+1)/2].sit+=8;
           }
           
        }
        fin.get();
	}        
        a[door1.x][door1.y].step1=1;
		//a[door1.x][door1.y].sit+=1;
        a[door2.x][door2.y].step2=1;
        now=door1;
        q.push(now);        
        while(!q.empty())
        {
            now=q.front();
            q.pop();
            now.step++;
            //step_now++;
            if((a[now.x][now.y].sit & 1) == 0 && now.x>0 && a[now.x-1][now.y].step1<0) 
                                   {now.x--;a[now.x][now.y].step1=now.step;q.push(now);now.x++;}
            if((a[now.x][now.y].sit & 2) == 0 && now.y<n-1 && a[now.x][now.y+1].step1<0) 
                                   {now.y++;a[now.x][now.y].step1=now.step;q.push(now);now.y--;}
            if((a[now.x][now.y].sit & 4) == 0 && now.x<m-1 && a[now.x+1][now.y].step1<0) 
                                   {now.x++;a[now.x][now.y].step1=now.step;q.push(now);now.x--;}
            if((a[now.x][now.y].sit & 8) == 0 && now.y>0 && a[now.x][now.y-1].step1<0) 
                                   {now.y--;a[now.x][now.y].step1=now.step;q.push(now);now.y++;}
        }
		now=door2;
        q.push(now);        
        while(!q.empty())
        {
            now=q.front();
            q.pop();
            now.step++;
            //step_now++;
            if((a[now.x][now.y].sit & 1) == 0 && now.x>0 && a[now.x-1][now.y].step2<0) 
                                   {now.x--;a[now.x][now.y].step2=now.step;q.push(now);now.x++;}
            if((a[now.x][now.y].sit & 2) == 0 && now.y<n-1 && a[now.x][now.y+1].step2<0) 
                                   {now.y++;a[now.x][now.y].step2=now.step;q.push(now);now.y--;}
            if((a[now.x][now.y].sit & 4) == 0 && now.x<m-1 && a[now.x+1][now.y].step2<0) 
                                   {now.x++;a[now.x][now.y].step2=now.step;q.push(now);now.x--;}
            if((a[now.x][now.y].sit & 8) == 0 && now.y>0 && a[now.x][now.y-1].step2<0) 
                                   {now.y--;a[now.x][now.y].step2=now.step;q.push(now);now.y++;}
        }
    for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			min=1000000;
			if(a[i][j].step1<a[i][j].step2) min=a[i][j].step1;
			else min=a[i][j].step2;
			if(min>max) max=min;
		}
    }
    fout<<max<<endl;
  //  system("PAUSE");
    return 0;
}