oj.uz

답안 #122394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122394 2019-06-28T06:58:04 Z 임유진(#2991) 로봇 (APIO13_robots) C++14
30 / 100
 3 ms 384 KB 
#include<stdio.h>
#include<queue>

using namespace std;

typedef pair<int, int> pii;

int movement[4][2]={{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
char m[12][12];
int rot[12][12];
int moveto[12][12][4];
int dp[144][144];

int main(){
	int N, W, H;
	int y[2], x[2];
	int ans=10001;

	scanf("%d%d%d", &N, &W, &H);
	for(int i=1; i<=H; i++) scanf("%s", m[i]+1);
	
	for(int i=0; i<=H+1; i++) m[i][0]=m[i][W+1]='x';
	for(int i=1; i<=W; i++) m[0][i]=m[H+1][i]='x';
	for(int i=1; i<=H; i++) for(int j=1; j<=W; j++){
		if(m[i][j]=='C') rot[i][j]=-1;
		else if(m[i][j]=='A') rot[i][j]=1;
		else rot[i][j]=0;
		if(m[i][j]=='1'){
			y[0]=i;
			x[0]=j;
		}
		else if(m[i][j]=='2'){
			y[1]=i;
			x[1]=j;
		}
	}
	/*
	for(int i=1; i<=H; i++){
		for(int j=1; j<=W; j++) printf("%d ", rot[i][j]);
		printf("\n");
	}
	*/

	queue<pii> q;
	for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) if(m[i][j]!='x'){
		for(int k=0; k<4; k++){
			int kk=(k+rot[i][j]+4)%4;
			if(m[i+movement[kk][0]][j+movement[kk][1]]=='x'){
				//printf("i=%d, j=%d, k=%d\n", i, j, k);
				moveto[i][j][k]=i*12+j;
				q.push(make_pair(i*12+j, k));
			}
			else moveto[i][j][k]=-1;
		}
	}
	/*
	printf("%d\n", q.size());
	for(int i=1; i<=H; i++){
		for(int j=1; j<=W; j++){
			printf("[");
			for(int k=0; k<4; k++){
				if(moveto[i][j][k]!=-1) printf("(%d, %d)", moveto[i][j][k]/12, moveto[i][j][k]%12);
				else printf("-");
			}
			printf("]");
		}
		printf("\n");
	}
	*/
	while(!q.empty()){
		pii t=q.front();
		q.pop();
		int k=t.second;
		int i=t.first/12-movement[k][0], j=t.first%12-movement[k][1];
		if(0<i&&i<=H&&0<j&&j<=W&&m[i][j]!='x'){
			int kk=(k-rot[i][j]+4)%4;
			//printf("i=%d, j=%d, k=%d, kk=%d\n", i, j, k, kk);
			if(moveto[i][j][kk]==-1){
				moveto[i][j][kk]=moveto[i+movement[k][0]][j+movement[k][1]][k];
				//if(i==2&&j==1) printf("t=(%d, %d)\n", t.first, t.second);
				q.push(make_pair(i*12+j, kk));
			}
		}
	}

	/*
	for(int i=1; i<=H; i++){
		for(int j=1; j<=W; j++){
			printf("[");
			for(int k=0; k<4; k++){
				if(moveto[i][j][k]!=-1) printf("(%d, %d)", moveto[i][j][k]/12, moveto[i][j][k]%12);
				else printf("-");
			}
			printf("]");
		}
		printf("\n");
	}
	*/

	for(int i=1; i<144; i++) for(int j=1; j<144; j++) dp[i][j]=-1;
	q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
	dp[ y[0]*12+x[0] ][ y[1]*12+x[1] ] = 0;
	while(!q.empty()){
		pii t=q.front();
		q.pop();
		//if(t.first==t.second) printf("[(%d, %d), (%d, %d)]\n", t.first / 12, t.first % 12, t.second/12, t.second%12);
		if(t.first==t.second){
			int i=t.first/12, j=t.first%12;
			for(int k=0; k<4; k++){
				int mt = moveto[i][j][k];
				if( dp[mt][mt] == -1 ) {
					dp[mt][mt] = dp[t.first][t.second] + 1;
					q.push(make_pair(mt, mt));
				}
			}
		}
		else {
			int i=t.first/12, j=t.first%12;
			for(int k=0; k<4; k++){
				int mt = moveto[i][j][k];
				if( dp[mt][t.second] == -1 ) {
					dp[mt][t.second] = dp[t.first][t.second] + 1;
					q.push( make_pair( mt, t.second) );
				}
			}
			i = t.second/12, j = t.second%12;
			for(int k=0; k<4; k++){
				int mt = moveto[i][j][k];
				if( dp[t.first][mt] == -1){
					dp[t.first][mt] = dp[t.first][t.second]+1;
					q.push( make_pair( t.first, mt) );
				}
			}
		}
	}

	for(int i=1; i<=H; i++) for(int j=1; j<=W; j++){
		int t=i*12+j;
		if( dp[t][t] != -1) ans = min(ans, dp[t][t]);
	}
	printf("%d", ans==10001?-1:ans);

	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &W, &H);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=H; i++) scanf("%s", m[i]+1);
                          ~~~~~^~~~~~~~~~~~~~
robots.cpp:101:23: warning: 'y[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
  q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
                   ~~~~^~~
robots.cpp:101:40: warning: 'x[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
  q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
                                 ~~~~~~~^~~~~
robots.cpp:101:26: warning: 'x[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
  q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
                   ~~~~~~~^~~~~
robots.cpp:101:37: warning: 'y[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
  q.push(make_pair(y[0]*12+x[0], y[1]*12+x[1]));
                                 ~~~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Execution timed out 3 ms 384 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Execution timed out 3 ms 384 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -