oj.uz

답안 #475745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475745 2021-09-24T00:08:20 Z CaroLinda Patkice II (COCI21_patkice2) C++14
30 / 110
 2000 ms 182244 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second
#define mkt make_tuple
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define pii pair<int,int>
#define mk make_pair
#define pb push_back
#define tiiii tuple<int,int,int, int>

const int MAX = 2010 ;
const int inf = 1e9+10 ;

using namespace std ;

int N , M ;
int dx[4] = { 0, 1 , 0 , -1} , dy[4] = {1,0,-1,0} ;
int grid[MAX][MAX] , dist[MAX][MAX][4] ;
tuple<int,int,int> par[MAX][MAX][4 ] ;
pair<int,int> S , T ;
priority_queue< tiiii , vector<tiiii>, greater<tiiii> > fila ;

bool valid(int x, int y) { return 1 <= min(x,y) && x <= N && y <= M; }

int main()
{
	scanf("%d %d", &N, &M ) ;
	for(int i = 1 ; i <= N ; i++ )
		for(int j = 1 ; j <= M ; j++ )
		{
			char c ;
			scanf(" %c", &c ) ;

			if(c == 'v') grid[i][j] = 1 ;
			if( c == '<' ) grid[i][j] = 2 ;
			if( c == '^' ) grid[i][j] = 3 ;

			if( c == 'o' ) S = mk(i,j) , grid[i][j] = -1 ;
			if( c == 'x' ) T = mk(i,j) , grid[i][j] = -2 ;
			if(c == '.') grid[i][j] = 4 ;
		}

	for(int i = 1 ; i <= N ; i++ )
		for(int j = 1 ; j <= M ; j++ )
			for(int g = 0 ; g < 4 ; g++ ) dist[i][j][g] = inf ;

	for(int g = 0 ; g < 4 ; g++ ) 
	{
		dist[S.first][S.second][g] = 0 ;
		fila.push( mkt(0, S.ff, S.ss,g) ) ;
	}

	tuple<int,int,int> cur ;

	while(!fila.empty())
	{
		int d = get<0>(fila.top()) ;
		int x = get<1>(fila.top()) ;
		int y = get<2>(fila.top());
		int g = get<3>(fila.top()) ;

		fila.pop() ;

		if( d != dist[x][y][g] ) continue ;

		if(x == T.ff && y == T.ss ) 
		{
			printf("%d\n" , dist[x][y][g]) ;
			cur = par[x][y][g] ;
			break ;
		}

		int nx = x + dx[g] ;
		int ny = y + dy[g] ;

		if(!valid(nx, ny)) continue ;

		for(int i = 0 , nd ; i < 4 ; i++ )
		{
			nd = dist[x][y][g] ;
			if( i != grid[nx][ny] && grid[nx][ny] >= 0 ) nd++ ;

			if(nd >= dist[nx][ny][i]) continue ;
			par[nx][ny][i] = mkt(x,y,g) ;
			fila.push( mkt( dist[nx][ny][i] = nd , nx, ny, i ) ) ;

		}

	}

	int x = get<0>(cur) , y = get<1>(cur) , g = get<2>(cur) ;

	while(!(mk(x,y) == S))
	{
		grid[x][y] = g ;
		cur = par[x][y][g] ;
		x = get<0>(cur) , y = get<1>(cur), g = get<2>(cur) ;
	}

	lp(i,1,N+1)
	{
		lp(j,1,M+1)
		{
			if( grid[i][j] == 0 ) printf(">") ;
			if( grid[i][j] == 1 ) printf("v") ;
			if( grid[i][j] == 2 ) printf("<") ;
			if( grid[i][j] == 3 ) printf("^") ;
			if( grid[i][j] == -1 ) printf("o") ;
			if( grid[i][j] == -2 ) printf("x") ;
			if( grid[i][j] == 4 ) printf(".") ;
		}
		printf("\n") ;
	}

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d %d", &N, &M ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |    scanf(" %c", &c ) ;
      |    ~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
0.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 428 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 258 ms 30672 KB Output is correct
7 Correct 244 ms 52132 KB Output is correct
8 Correct 886 ms 82556 KB Output is correct
9 Correct 1593 ms 170048 KB Output is correct
10 Execution timed out 2098 ms 182244 KB Time limit exceeded
11 Halted 0 ms 0 KB -