글 읽기 - 반례가 있을까요 ㅠㅠ?

domoosu 5년 전 0

밑에있는

도 맞고

50개도 다해보고 막아도 보고 해봤는데

다 제대로 나오는거같은데 뭐가 문제일까요..

bfs로해서 S-c1-c2 와

s-c2-c1 두개를 비교해서

최소값으로 나오도록 했는데, 70퍼쯤에서 틀렸다고 나오네요..ㅠㅠㅠㅠ

#include <iostream>
#include <queue>

using namespace std;

char map[51][51];
bool visit[51][51][4];

int N, M;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int dir;

int qu(int my, int mx, int cy, int cx, int dd);

int main()
{
	int my, mx;
	int x[2], y[2], idx = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int m = 0; m < M; m++) {
			cin >> map[i][m];
			if (map[i][m] == 'S')
			{
				my = i, mx = m;
			}
			if (map[i][m] == 'C')
			{
				y[idx] = i, x[idx] = m;
				idx++;
			}
		}
	}

	int fi = qu(my, mx, y[0], x[0], 100);
	int se = qu(y[0], x[0], y[1], x[1], dir);
	int th = qu(my, mx, y[1], x[1], 100);
	int fo = qu(y[1], x[1], y[0], x[0], dir);
	int ans;
	if ((fi == -1 || se == -1) && (th == -1 || fo == -1))
	{
		cout << -1 << endl;
		return 0;
	}
	if (fi + se < th + fo) ans = fi + se;
	else ans = th + fo;

	cout << ans << endl;

	return 0;
}

int qu(int my, int mx, int ddy, int ddx, int dd)
{
	for (int i = 0; i < N; i++) {
		for (int m = 0; m < M; m++) {
			for (int k = 0; k < 4; k++) {
				visit[i][m][k] = false;
			}
		}
	}

	queue<int> qy, qx, qt, qc, qr;
	int cy, cx, ct, cc, nc, ny, nx, nt, cr, nr;

	qy.push(my); qx.push(mx); qt.push(0); qr.push(dd);

	while (!qy.empty())
	{
		cy = qy.front(); qy.pop();
		cx = qx.front(); qx.pop();
		ct = qt.front(); qt.pop();
		cr = qr.front(); qr.pop();

		if (map[cy][cx] == '#') continue;
		if (cy==ddy&&cx==ddx) {
			dir = cr;
			return ct;
		}

		for (int i = 0; i < 4; i++)
		{
			ny = cy + dy[i]; nx = cx + dx[i];
			if (ny >= N || nx >= M || nx < 0 || ny < 0) continue;
			if (cr == i) continue;
			if (visit[cy][cx][i] == true) continue;
			visit[cy][cx][i] = true;

			qy.push(ny); qx.push(nx); qt.push(ct + 1);
			qr.push(i);
		}
	}

	return -1;
}

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

문제

문제

출처

ICPC

반례가 있을까요 ㅠㅠ?

domoosu 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말