?? 1033.cpp
字號:
//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;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -