Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:该死,本机上运行好好的,一提交就Compile Error,找不出错啊,都做了100多道题了,第一次遇到这种情况。。。

Posted by master_wugui at 2011-10-09 22:54:59 on Problem 2312
In Reply To:该死,本机上运行好好的,一提交就Compile Error,找不出错啊,都做了100多道题了,第一次遇到这种情况。。。 Posted by:master_wugui at 2011-10-09 22:53:49
#include <iostream>
using namespace std;

const int Max = 300;
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };

// 对象
int M, N;
char map[Max][Max];
int or, oc; // 起点
struct State {
	int r,c;
	bool f; // fire:是否已开火
}Q[Max*10]; // Open表
int visit[Max][Max]; // Close表,同时记录已走距离

// 函数
bool IsReachable( const int r, const int c )
{
	if( !(r >= 0 && r < M && c >= 0 && c < N) || 
		map[r][c] == 'S' || map[r][c] == 'R' || visit[r][c] >= 0 ) return false;
	else return true;
}
int BFS()
{
	// 初始化
	memset( visit, -1, sizeof(visit) );
	memset( Q, 0, sizeof(Q) );
	visit[or][oc] = 0;
	int front = 0, rear = 0;
	// 起点入队
	Q[rear].r = or, Q[rear].c = oc, ++ rear;

	// BFS
	while( front < rear ) {
		State top = Q[front++];
		bool isFire = false; // 标记是否需要开火
		// 4方向扩展+开火扩展
		for( int i = 0; i < 4; ++ i ) {
			int nr = top.r + dir[i][0];
			int nc = top.c + dir[i][1];
			// 不可达
			if( !IsReachable( nr, nc ) ) continue;
			// 终点
			if( map[nr][nc] == 'T' ) return visit[top.r][top.c] + 1;
			// 可达
			if( map[nr][nc] == 'E' || map[nr][nc] == 'B' && top.f ) {
				Q[rear].r = nr, Q[rear].c = nc, ++ rear; // 扩展
				visit[nr][nc] = visit[top.r][top.c] + 1; // 记录
			}
			else if( map[nr][nc] == 'B' && !top.f ) 
				isFire = true;
		}
		if( isFire ) {
			Q[rear] = top, Q[rear].f = true, ++ rear;
			++ visit[top.r][top.c];
		}
	}
	return -1;
}

int main()
{
	while( scanf( "%d%d", & M, & N ) &&  M+N > 0 ) {
		for( int i = 0; i < M; ++ i ) {
			getchar();
			for( int j = 0; j < N; ++ j ) {
				scanf( "%c", & map[i][j] );
				if( map[i][j] == 'Y' )
					or = i, oc = j;
			}
		}
		cout << BFS() << "\n";
	}
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator