#90999 (C90) No.367 ナイトの転身

提出ソース

結果

問題	No.367 ナイトの転身
ユーザー	kapo
提出日時	2016-05-10 15:32:29
言語	C90 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	5,063 bytes
コンパイル時間	162 ms
コンパイル使用メモリ	23,808 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-15 15:04:59
合計ジャッジ時間	1,005 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	AC	1 ms 5,376 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	1 ms 5,376 KB
testcase_06	WA	-
testcase_07	AC	0 ms 5,376 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

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]);
      |                                 ^~~~~~~~~~~~~~~~~~

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード