AOJ 0558：Cheese(bfs)

링크 열기
H * W 의 지도 에는 N 개의 치즈 공장 이 있 는데 각각 경도 가 1 - N 인 치즈 를 생산 한다.한 마리 의 먹 방 쥐 가 쥐구멍 에서 출발 하여 모든 공장 의 치즈 를 다 먹 으 려 고 한다.
쥐 는 하나의 체력 치 를 가지 고 있 으 며, 초기 에는 1 이 었 으 며, 한 공장 의 치즈 를 먹 을 때마다 체력 치가 1 (공장 당 한 번 만 먹 을 수 있 음) 증가 하 였 으 며, 쥐 는 현재 체력 치보다 경도 가 높 지 않 은 치즈 만 먹 을 수 있 었 다.
쥐 는 현재 칸 에서 인접 한 무장 애 물의 칸 (상하 좌우) 까지 시간 1 단위 가 필요 하 며, 장애물 이 있 는 칸 은 갈 수 없다.공장 에 도착 하면 이 공장 의 치즈 를 먹 을 수 있 고 치즈 를 먹 는 시간 은 따 지지 않 는 다.모든 치즈 를 다 먹 었 을 때 가장 적 게 쓸 때.
입력:
첫 줄 에 세 개의 정수 HW N.
그 다음 에 H 행 W 가 지도 로 되 어 있어 요.
그 중에서 "." 공 터 입 니 다. "X" 는 장애물 입 니 다. "S" 는 쥐구멍 입 니 다. 1 - N 은 경도 가 1 - N 인 치즈 공장 을 대표 합 니 다.
 
문제 규모:
1 <= W, H <= 1000
1 <= N <= 9
 
입력:
3 3 1
S..
...
..1
  
출력:
14
   
입력:
4 5 2
.X..1
....X
.XX.S
.2.X.
  
출력:
12
   
 
입력:
10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......
  
출력:
91
 
답:
 

#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX_W 1000
#define MAX_H 1000
#define MAX_N 9

using namespace std;

char m[MAX_H][MAX_W + 1];
int w, h, n;
int gx[MAX_N + 1], gy[MAX_N + 1];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

int bfs(int sx, int sy, int gx, int gy)
{
	int d[MAX_H][MAX_W];
	memset(d, -1, sizeof(d));
	queue<int> que;
	que.push(sx * w + sy);
	d[sx][sy] = 0;
		
	while(que.size())
	{
		int x = que.front()/w, y = que.front()%w;
		que.pop();
		if(x == gx && y == gy)
			break;

		for(int di = 0; di < 4; ++di){
			int nx = x + dx[di], ny = y + dy[di];
			if(nx >= 0 && nx < h && ny >= 0 && ny < w && 'X' != m[nx][ny] && -1 == d[nx][ny]){
				d[nx][ny] = d[x][y] + 1;
				que.push(nx * w + ny);
			}
		}
	}
	return d[gx][gy];
}

void solve()
{
	int ans = 0;
	for(int i = 0; i < n; i ++)
		ans += bfs(gx[i], gy[i], gx[i + 1], gy[i + 1]);
	printf("%d
", ans);
}

int main()
{
	scanf("%d%d%d", &h, &w, &n);
	for(int i = 0; i < h; i ++)
		scanf("%s", m[i]);
		
	for(int i = 0; i < h; i ++)
		for(int j = 0; j < w; j ++){
			if('1' <= m[i][j] && '9' >= m[i][j])
				gx[m[i][j] - '0'] = i, gy[m[i][j] - '0'] = j;
			else if('S' == m[i][j])
				gx[0] = i, gy[0] = j;
		}

	if(w || h)
		solve();
	return 0;
}

이 이 치 는 나 를 매우 우울 하 게 한다. 우선 입력 양식 을 잘 보지 못 해서 HW N 을 W H N 으로 보 았 기 때문이다.
그 다음 에 scanf ("% c",...) 를 사용 하여 하나씩 입력 하고 gets 줄 을 입력 해서 무슨 오류 가 발생 했 는 지 모 르 기 때문에 출력 입력 흐름 이 너무 번 거 롭 습 니 다.
그리고 Dev - C + + 의 스 택 공간 이 제한 되 어 있 기 때문에 매번 bfs 함 수 를 실행 할 때마다 알 수 없 는 프로그램 이 중단 되 어 저 는 오랫동안 디 버 깅 을 했 습 니 다.