12851번 - 숨바꼭질 2
#include <stdio.h>#include <queue>
using namespace std;
int visit[200001], visit_num[200001] = { 0 };int main() { int n, k, c_pos, c_cost, npos; int i; queue<int> pos, cost; scanf("%d %d", &n, &k);
pos.push(n); cost.push(0);
for (i = 0; i <= 200000; i++) visit[i] = 99999; visit[n] = 0; visit_num[n] = 1;
while (!pos.empty()) { c_pos = pos.front(); c_cost = cost.front();
npos = c_pos - 1; if (npos >= 0 && npos <= 200000) { if (visit[npos] > c_cost + 1) { pos.push(npos); cost.push(c_cost + 1); visit[npos] = c_cost + 1; visit_num[npos] = visit_num[c_pos]; } else if(visit[npos] == c_cost + 1) visit_num[npos]+=visit_num[c_pos]; }
npos = c_pos + 1; if (npos >= 0 && npos <= 200000) { if (visit[npos] > c_cost + 1) { pos.push(npos); cost.push(c_cost + 1); visit[npos] = c_cost + 1; visit_num[npos] = visit_num[c_pos]; } else if (visit[npos] == c_cost + 1) visit_num[npos] += visit_num[c_pos]; }
npos = c_pos * 2; if (npos >= 0 && npos <= 200000) { if (visit[npos] > c_cost + 1) { pos.push(npos); cost.push(c_cost + 1); visit[npos] = c_cost + 1; visit_num[npos] = visit_num[c_pos]; } else if (visit[npos] == c_cost + 1) visit_num[npos] += visit_num[c_pos]; }
pos.pop(); cost.pop(); }
printf("%d\n%d", visit[k], visit_num[k]);}
100000 0 넣어보세용
댓글을 작성하려면 로그인해야 합니다.
janghoy100 7년 전
#include <stdio.h>
#include <queue>
using namespace std;
int visit[200001], visit_num[200001] = { 0 };
int main() {
int n, k, c_pos, c_cost, npos;
int i;
queue<int> pos, cost;
scanf("%d %d", &n, &k);
pos.push(n);
cost.push(0);
for (i = 0; i <= 200000; i++) visit[i] = 99999;
visit[n] = 0;
visit_num[n] = 1;
while (!pos.empty()) {
c_pos = pos.front();
c_cost = cost.front();
npos = c_pos - 1;
if (npos >= 0 && npos <= 200000) {
if (visit[npos] > c_cost + 1) {
pos.push(npos);
cost.push(c_cost + 1);
visit[npos] = c_cost + 1;
visit_num[npos] = visit_num[c_pos];
}
else if(visit[npos] == c_cost + 1) visit_num[npos]+=visit_num[c_pos];
}
npos = c_pos + 1;
if (npos >= 0 && npos <= 200000) {
if (visit[npos] > c_cost + 1) {
pos.push(npos);
cost.push(c_cost + 1);
visit[npos] = c_cost + 1;
visit_num[npos] = visit_num[c_pos];
}
else if (visit[npos] == c_cost + 1) visit_num[npos] += visit_num[c_pos];
}
npos = c_pos * 2;
if (npos >= 0 && npos <= 200000) {
if (visit[npos] > c_cost + 1) {
pos.push(npos);
cost.push(c_cost + 1);
visit[npos] = c_cost + 1;
visit_num[npos] = visit_num[c_pos];
}
else if (visit[npos] == c_cost + 1) visit_num[npos] += visit_num[c_pos];
}
pos.pop();
cost.pop();
}
printf("%d\n%d", visit[k], visit_num[k]);
}