1033.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//BFS
//be care of the boundary!!
#include <iostream>
#include <queue>
using namespace std;
const int maxN = 33;
const int maxint = 0x0f0f0f0f;
int map[maxN + 3][maxN + 3];
bool isVisit[maxN + 3][maxN + 3];
int n,num;

struct Point{ int x,y; };
void readIn()
{
     memset( map, 15, sizeof(map) );
     int i, j;
     char ch;
     cin >> n;
     for( i = 1; i <= n; i++ )
          for( j = 1; j <= n; j++ )
          {
               cin >> ch;
               if( ch == '.' ) map[i][j] = 0;
               else if( ch == '#' ) map[i][j] = 1;
          }
/*     cout << map[0][0] << endl;
     for( i = 1; i <= n; i++ ){
          for( j = 1; j <= n; j++ )
               cout << map[i][j] << ' ';
          cout << endl;
          }*/
}

void work()
{
     queue<Point> Q;
     Point p1,p2,pt,pnext;
     p1.x = 1,p1.y = 1; p2.x = n, p2.y = n;
     memset( isVisit, false, sizeof(isVisit) );
     Q.push(p1);
     Q.push(p2);
     isVisit[p1.x][p1.y] = true;
     isVisit[p2.x][p2.y] = true;
     num = -4; // 一开始有4块地方是空的 
     while( !Q.empty() )
     {
            pt = Q.front();
            Q.pop();
            if( map[pt.y][pt.x - 1] != 0 ) num++;
            if( map[pt.y][pt.x + 1] != 0 ) num++;           
            if( map[pt.y - 1][pt.x] != 0 ) num++;             
            if( map[pt.y + 1][pt.x] != 0 ) num++;
//            cout << pt.x << ' ' << pt.y << " : " << num <<endl;
            if( map[pt.y][pt.x - 1] == 0 && isVisit[pt.y][pt.x - 1] == false ) { pnext.x = pt.x - 1, pnext.y = pt.y; isVisit[pnext.y][pnext.x] = true; Q.push(pnext); } 
            if( map[pt.y][pt.x + 1] == 0 && isVisit[pt.y][pt.x + 1] == false ) { pnext.x = pt.x + 1, pnext.y = pt.y; isVisit[pnext.y][pnext.x] = true; Q.push(pnext); }             
            if( map[pt.y - 1][pt.x] == 0 && isVisit[pt.y - 1][pt.x] == false ) { pnext.x = pt.x, pnext.y = pt.y - 1; isVisit[pnext.y][pnext.x] = true; Q.push(pnext); }             
            if( map[pt.y + 1][pt.x] == 0 && isVisit[pt.y + 1][pt.x] == false ) { pnext.x = pt.x, pnext.y = pt.y + 1; isVisit[pnext.y][pnext.x] = true; Q.push(pnext); }             
     }        
}
int main()
{
//    freopen( "1033.in", "r", stdin );
//    freopen( "1033.out","w", stdout );
    readIn();
    work();
    cout << num * 9 <<endl;
    return 0;
}