Submission #1419705
Source Code Expand
#include <stdio.h>
#include <stdlib.h>
int r, c, sy, sx, gy, gx;
char cells[50][50];
int dist[50][50];
struct node {
struct node *prev;
int y;
int x;
};
struct queue {
struct node *head;
struct node *last;
};
struct queue *queue_create(void) {
struct queue *q;
q = malloc(sizeof(struct queue));
q->head = NULL;
q->last = NULL;
return q;
}
struct node *queue_pop(struct queue *q) {
struct node *n;
n = q->last;
if (q->last) {
q->last = q->last->prev;
if (!q->last)
q->head = NULL;
}
return n;
}
void queue_print(struct queue *q) {
int i = 0;
struct node *n;
n = q->last;
printf("nodes: ");
while (n) {
printf("(%d, %d) ", n->y, n->x);
n = n->prev;
}
printf("\n");
}
void queue_push(struct queue *q, struct node *n) {
if (q->head)
q->head->prev = n;
else
q->last = n;
q->head = n;
}
struct node *node_create(void) {
struct node *n;
n = malloc(sizeof(struct node));
n->prev = NULL;
n->y = -1;
n->x = -1;
return n;
}
void node_destroy(struct node *n) {
free(n);
}
struct queue *q;
void dist_print(void) {
int i, j;
for (i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j)
if (cells[i][j] == '.' && dist[i][j] != -1)
printf("%3d", dist[i][j]);
else
printf(" %c", cells[i][j]);
printf("\n");
}
}
int main(void) {
int i, j, d, yy, xx;
struct node *n, *n2;
int dy[] = {-1, 0, 0, 1};
int dx[] = {0, -1, 1, 0};
scanf("%d%d%d%d%d%d", &r, &c, &sy, &sx, &gy, &gx);
--sy;
--sx;
--gy;
--gx;
for (i = 0; i < r; ++i)
for (j = 0; j < c; ++j) {
scanf(" %c", &cells[i][j]);
dist[i][j] = -1;
}
q = queue_create();
n = node_create();
n->y = sy;
n->x = sx;
queue_push(q, n);
dist[n->y][n->x] = 0;
while(1) {
n = queue_pop(q);
if (!n) break;
d = dist[n->y][n->x];
for (i = 0; i < 4; ++i) {
yy = n->y + dy[i];
xx = n->x + dx[i];
if (cells[yy][xx] == '.' && dist[yy][xx] == -1) {
n2 = node_create();
n2->y = yy;
n2->x = xx;
queue_push(q, n2);
dist[n2->y][n2->x] = d + 1;
}
}
node_destroy(n);
}
printf("%d\n", dist[gy][gx]);
return 0;
}
Submission Info
Submission Time
2017-07-14 00:59:38+0900
Task
C - 幅優先探索
User
test20170101
Language
C (GCC 5.4.1)
Score
100
Code Size
3191 Byte
Status
AC
Exec Time
1 ms
Memory
128 KB
Compile Error
./Main.c: In function ‘main’:
./Main.c:91:9: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d%d", &r, &c, &sy, &sx, &gy, &gx);
^
./Main.c:98:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &cells[i][j]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
100 / 100
Status
Set Name
Test Cases
Sample
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name
Status
Exec Time
Memory
subtask0_sample01.txt
AC
1 ms
128 KB
subtask0_sample02.txt
AC
1 ms
128 KB
subtask0_sample03.txt
AC
1 ms
128 KB
subtask1_01.txt
AC
1 ms
128 KB
subtask1_02.txt
AC
1 ms
128 KB
subtask1_03.txt
AC
1 ms
128 KB
subtask1_04.txt
AC
1 ms
128 KB
subtask1_05.txt
AC
1 ms
128 KB
subtask1_06.txt
AC
1 ms
128 KB
subtask1_07.txt
AC
1 ms
128 KB
subtask1_08.txt
AC
1 ms
128 KB
subtask1_09.txt
AC
1 ms
128 KB
subtask1_10.txt
AC
1 ms
128 KB
subtask1_11.txt
AC
1 ms
128 KB
subtask1_12.txt
AC
1 ms
128 KB
subtask1_13.txt
AC
1 ms
128 KB
subtask1_14.txt
AC
1 ms
128 KB
subtask1_15.txt
AC
1 ms
128 KB
subtask1_16.txt
AC
1 ms
128 KB
subtask1_17.txt
AC
1 ms
128 KB
subtask1_18.txt
AC
1 ms
128 KB
subtask1_19.txt
AC
1 ms
128 KB
subtask1_20.txt
AC
1 ms
128 KB
subtask1_21.txt
AC
1 ms
128 KB
subtask1_22.txt
AC
1 ms
128 KB