結果
| 問題 |
No.367 ナイトの転身
|
| コンテスト | |
| ユーザー |
 kapo
|
| 提出日時 | 2016-05-10 15:32:29 |
| 言語 | C90 (gcc 12.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,063 bytes |
| コンパイル時間 | 428 ms |
| コンパイル使用メモリ | 23,936 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-10-05 13:29:46 |
| 合計ジャッジ時間 | 1,227 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 WA * 24 |
コンパイルメッセージ
main.c: In function ‘dequeue’:
main.c:70:16: warning: function returns address of local variable [-Wreturn-local-addr]
70 | return pos;
| ^~~
main.c: In function ‘main’:
main.c:86:41: warning: format ‘%s’ expects argument of type ‘char *’, but argument 2 has type ‘char (*)[501]’ [-Wformat=]
86 | for( i = 0; i < h; i++) scanf("%s", &b[i]);
| ~^ ~~~~~
| | |
| | char (*)[501]
| char *
main.c:85:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
85 | scanf("%d %d", &h, &w);
| ^~~~~~~~~~~~~~~~~~~~~~
main.c:86:33: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
86 | for( i = 0; i < h; i++) scanf("%s", &b[i]);
| ^~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int front, rear, count, size, **buf;
} Queue;
Queue *make_q(int n)
{
Queue *que = (Queue *)malloc(sizeof(Queue));
if( que != NULL ) {
que->front = 0;
que->rear = 0;
que->count = 0;
que->size = n*10;
que->buf = (int **)malloc(sizeof(int) * n*10*4 );
if( que->buf == NULL ) {
free(que);
return NULL;
}
int i;
for( i = 0; i < n*10; i++) {
que->buf[i] = (int *)malloc(sizeof(int) * 4);
if( que->buf[i] == NULL) {
free(que);
return NULL;
}
}
}
return que;
}
int is_full( Queue *que)
{
return que->count == que->size;
}
int enqueue( Queue *que, int pos[4])
{
if( is_full(que) ) return 0;
int i;
for( i = 0; i < 4; i++) {
que->buf[que->rear][i] = pos[i];
}
que->rear++;
que->count++;
if( que->rear == que->size)
que->rear = 0;
return 1;
}
int is_empty( Queue *que )
{
return que->count == 0;
}
int *dequeue( Queue *que, int *err)
{
if( is_empty(que)) {
*err = 0;
return 0;
}
int pos[4] = { que->buf[que->front][0], que->buf[que->front][1],
que->buf[que->front][2], que->buf[que->front][3] };
que->front++;
que->count--;
*err = 1;
if( que->front == que->size )
que->front = 0;
return pos;
}
int main(void)
{
int i, j, h, w, *kb, *bb, is_knight = 1;
if( (kb = (int *)calloc(25000, sizeof(int *))) == NULL) {
return 0;
}
if( (bb = (int *)calloc(25000, sizeof(int *))) == NULL) {
return 0;
}
char b[500][501];
scanf("%d %d", &h, &w);
for( i = 0; i < h; i++) scanf("%s", &b[i]);
Queue *que = make_q( h );
int err;
for( i = 0; i < h; i++ ) {
for( j = 0; j < w; j++) if( b[i][j] == 'S' ) {
int pos[4] = { i, j, 0, is_knight };
enqueue(que, pos);
}
}
int *a;
if( (a = (int *)malloc(sizeof(int)*4)) == NULL) return 0;
while( (a = dequeue( que, &err )) != 0 ) {
int y = a[0], x = a[1], node = a[2], is_knight = a[3];
if( b[y][x] == 'R' ) {
if( is_knight ) { is_knight = 0; }
else if( !is_knight ) { is_knight = 1; }
}
if( is_knight ) {
if( y-2 >= 0 && h > y-2 && x-1 >= 0 && w > x-1 && (kb[(y-2)*500+(x-1)] == 0 || kb[(y-2)*500+(x-1)] > node+1)) {
kb[(y-2)*500+(x-1)] = node+1;
int pos[4] = {y-2, x-1, node+1, is_knight};
enqueue(que, pos);
}
if( y-2 >= 0 && h > y-2 && x+1 >= 0 && w > x+1 && (kb[(y-2)*500+(x+1)] == 0 || kb[(y-2)*500+(x+1)] > node+1)) {
kb[(y-2)*500+(x+1)] = node+1;
int pos[4] = {y-2, x+1, node+1, is_knight};
enqueue(que, pos);
}
if( y-1 >= 0 && h > y-1 && x-2 >= 0 && w > x-2 && (kb[(y-1)*500+(x-2)] == 0 || kb[(y-1)*500+(x-2)] > node+1)) {
kb[(y-1)*500+(x-2)] = node+1;
int pos[4] = {y-1, x-2, node+1, is_knight};
enqueue(que, pos);
}
if( y-1 >= 0 && h > y-1 && x+2 >= 0 && w > x+2 && (kb[(y-1)*500+(x+2)] == 0 || kb[(y-1)*500+(x+2)] > node+1)) {
kb[(y-1)*500+(x+2)] = node+1;
int pos[4] = {y-1, x+2, node+1, is_knight};
enqueue(que, pos);
}
if( y+1 >= 0 && h > y+1 && x-2 >= 0 && w > x-2 && (kb[(y+1)*500+(x-2)] == 0 || kb[(y+1)*500+(x-2)] > node+1)) {
kb[(y+1)*500+(x-2)] = node+1;
int pos[4] = {y+1, x-2, node+1, is_knight};
enqueue(que, pos);
}
if( y+1 >= 0 && h > y+1 && x+2 >= 0 && w > x+2 && (kb[(y+1)*500+(x+2)] == 0 || kb[(y+1)*500+(x+2)] > node+1)) {
kb[(y+1)*500+(x+2)] = node+1;
int pos[4] = {y+1, x+2, node+1, is_knight};
enqueue(que, pos);
}
if( y+2 >= 0 && h > y+2 && x-1 >= 0 && w > x-1 && (kb[(y+2)*500+(x-1)] == 0 || kb[(y+2)*500+(x-1)] > node+1)) {
kb[(y+2)*500+(x-1)] = node+1;
int pos[4] = {y+2, x-1, node+1, is_knight};
enqueue(que, pos);
}
if( y+2 >= 0 && h > y+2 && x+1 >= 0 && w > x+1 && (kb[(y+2)*500+(x+1)] == 0 || kb[(y+2)*500+(x+1)] > node+1)) {
kb[(y+2)*500+(x+1)] = node+1;
int pos[4] = {y+2, x+1, node+1, is_knight};
enqueue(que, pos);
}
}
if( !is_knight ) {
if( y-1 >= 0 && h > y-1 && x-1 >= 0 && w > x-1 && (bb[(y-1)*500+(x-1)] == 0 || bb[(y-1)*500+(x-1)] > node+1)) {
bb[(y-1)*500+(x-1)] = node+1;
int pos[4] = {y-1, x-1, node+1, is_knight};
enqueue(que, pos);
}
if( y-1 >= 0 && h > y-1 && x+1 >= 0 && w > x+1 && (bb[(y-1)*500+(x+1)] == 0 || bb[(y-1)*500+(x+1)] > node+1)) {
bb[(y-1)*500+(x+1)] = node+1;
int pos[4] = {y-1, x+1, node+1, is_knight};
enqueue(que, pos);
}
if( y+1 >= 0 && h > y+1 && x+1 >= 0 && w > x+1 && (bb[(y+1)*500+(x+1)] == 0 || bb[(y+1)*500+(x+1)] > node+1)) {
bb[(y+1)*500+(x+1)] = node+1;
int pos[4] = {y+1, x+1, node+1, is_knight};
enqueue(que, pos);
}
if( y+1 >= 0 && h > y+1 && x-1 >= 0 && w > x-1 && (bb[(y+1)*500+(x-1)] == 0 || bb[(y+1)*500+(x-1)] > node+1)) {
bb[(y+1)*500+(x-1)] = node+1;
int pos[4] = {y+1, x-1, node+1, is_knight};
enqueue(que, pos);
}
}
}
int goal = 0;
for( i = 0; i < h; i++){
for( j = 0; j < w; j++){
if( b[i][j] == 'G') {
goal = kb[i*500+j];
if( bb[i*500+j] != 0 && bb[i*500+j] < goal ) goal = bb[i*500+j];
}
}
}
if( !goal ) {
printf("-1\n");
return 0;
}
printf("%d\n", goal);
free(que);
free(kb);
free(bb);
return 0;
}