6044: 울 음 과 보좌

1662 단어 poj
http://noi.openjudge.cn/ch0205/6044/ 여전히 BFS 프레임 워 크 이지 만 여기 새로운 제약 조건 이 있 습 니 다. 차 크 라 이기 때문에 상태 매개 변 수 는 R (x, y, k) 이 어야 합 니 다. 같은 x, y 가 서로 다른 차 크 라 가 있 으 면 서로 다른 상태 에 대응 해 야 합 니 다.이 점 만 주의 하면 된다.
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

struct State {
	int x, y, k, t;
	State() {};
	State(int xx, int yy, int kk, int tt) :x(xx), y(yy), k(kk), t(tt) {};
};

queue q;
bool flag[210][210][11];
char maze[210][210];
int M, N, T,endi,endj;
int to[4][2] = { 0,1,1,0,0,-1,-1,0 };

int main() {
	scanf("%d%d%d
", &M, &N, &T); for (int i = 0;i < M;i++) { for (int j = 0;j < N;j++) { scanf("%c", &maze[i][j]); if (maze[i][j] == '@') { q.push(State(i, j, T, 0)); } if (maze[i][j] == '+') { endi = i; endj = j; } } getchar(); } bool success = false; while (!q.empty()) { State s = q.front(); if (s.x == endi && s.y == endj) { printf("%d", s.t); success = true; break; } for (int t = 0;t < 4;t++) { int x = s.x + to[t][0]; int y = s.y + to[t][1]; if (x >= 0 && x < M && y >= 0 && y < N) { if (maze[x][y] == '#'&&s.k <1) { continue; } int k = maze[x][y] == '#' ? s.k - 1 : s.k; if (!flag[x][y][k]) { flag[x][y][k] = 1; q.push(State(x, y, k, s.t + 1)); } } } q.pop(); } if (!success) { printf("-1"); } return 0; }

좋은 웹페이지 즐겨찾기