글 읽기 - 반례를 모르겠습니다 ㅠㅠ

fuck5203 5년 전 0

반례를 못찾겠습니다..게시판에 있는 반례 모두 해봤는데도요...도움좀 부탁드립니다!

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct node {
	bool loc; 
	int malnum=0; //남은 말의 횟수
	int count = -1; // 이 좌표까지 오는데 걸린 횟수
};
struct coor {
	int x;
	int y;
	int malnum;
	int count;
};
node map[205][205];
bool visit[205][205][31];
int K, W, H; // W = x, H = y;
int mal_x[8] = { 1,2,1,2,-1,-2,-1,-2 };
int mal_y[8] = { -2,-1,2,1,2,1,-2,-1 };
int m_x[4] = {0,0,1,1};
int m_y[4] = { 1,-1,0,0 };
queue<coor> q;

bool isRange(int y, int x) {
	if (x > 0 && y > 0 && x <= W && y <= H)
		return true;
	else
		return false;
}
void bfs() {
	coor start;
	start.count = 0;
	start.malnum = K;
	start.x = 1;
	start.y = 1;

	visit[1][1][K] = true;
	q.push(start);
	while (!q.empty()) {
		int x, y,mal,c;
		x = q.front().x;
		y = q.front().y;
		mal = q.front().malnum;
		c = q.front().count;
		q.pop();
		if (x == W && y == H) {
			if (map[y][x].count != -1) {
				map[y][x].count = min(map[y][x].count, c);
			}
			else {
				map[y][x].count = c;
			}
			continue;
		}

		for (int i = 0; i < 4; i++) {
			if (isRange(y+m_y[i],x+m_x[i]) && !map[y + m_y[i]][x + m_x[i]].loc && !visit[y+m_y[i]][x+m_x[i]][mal]) {
				visit[y + m_y[i]][x + m_x[i]][mal] = true;
				coor loc;
				loc.count = c + 1;
				loc.malnum = mal;
				loc.x = x+m_x[i];
				loc.y = y + m_y[i];
				
				
			
				q.push(loc);
			}
		}
		if (mal > 0) {
			for (int i = 0; i < 8; i++) {
				int next_y = y + mal_y[i];
				int next_x = x + mal_x[i];
				if (isRange(next_y, next_x) && !map[next_y][next_x].loc && !visit[next_y][next_x][mal - 1]) {
					visit[next_y][next_x][mal-1] = true;
					coor loc;
					loc.count = c + 1;
					loc.malnum = mal - 1;
					loc.x = next_x;
					loc.y = next_y;
					
					q.push(loc);
				}
			}
		}
	}
}

int main() {
	cin >> K;	
	cin >> W >> H;
	map[1][1].malnum = K;
	for (int i = 1; i <= H;i++) {
		for (int j = 1; j <= W; j++) {
			cin >> map[i][j].loc;
		}
	}
	
	bfs();

	if (map[H][W].count == -1) {
		cout << "-1";
		
	}
	else
		cout << map[H][W].count;

	return 0;
}

djm03178 5년 전 1

23번째 줄을 잘 보세요.

fuck5203 5년 전 0

헉...감사하고 민망하네요...하............이런거 고쳐야하는데

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 모르겠습니다 ㅠㅠ

fuck5203 5년 전 0

djm03178 5년 전 1

fuck5203 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말