| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 280263 | 2020-08-22T15:19:10 Z | antontsiorvas | Awesome Arrowland Adventure (eJOI19_adventure) | C++14 | 0 ms | 0 KB |
#include <cstdio>
#include <vector>
char ways[5] = {'X', 'N', 'E', 'S', 'W'};
bool visited[4][4];
int find_rots(char a, char b){
if(a == 'N'){
if(b == 'N') return 0;
if(b == 'E') return 1;
if(b == 'S') return 2;
if(b == 'W') return 3;
}
if(a == 'E'){
if(b == 'N') return 3;
if(b == 'E') return 0;
if(b == 'S') return 1;
if(b == 'W') return 2;
}
if(a == 'S'){
if(b == 'N') return 2;
if(b == 'E') return 3;
if(b == 'S') return 0;
if(b == 'W') return 1;
}
if(a == 'W'){
if(b == 'N') return 1;
if(b == 'E') return 2;
if(b == 'S') return 3;
if(b == 'W') return 0;
}
return 0;
}
bool find_path(char data[][3]){
int r=0, c=0;
while(1){
if(visited[r][c] || data[r][c] == 'X' || r < 0 || r > 2 || c < 0 || c > 2) return false;
visited[r][c] = true;
if(data[r][c] == 'F') return true;
if(data[r][c] == 'N') r--;
if(data[r][c] == 'E') c++;
if(data[r][c] == 'S') r++;
if(data[r][c] == 'W') c--;
}
}
int find_diff_rots(char s[][505], char d[][3]){
int ret = 0;
for(int i=0; i<3; i++){
for(int j=0; j<3; j++) ret += find_rots(s[i][j],d[i][j]);
}
return ret;
}
int main(){
int rows, cols, ans = 0;
char sym[505][505], send[3][3];
scanf("%d%d",&rows,&cols);
for(int i=0; i<rows; i++) scanf("\n%s",sym[i]);
sym[rows-1][cols-1] = 'F';
if(rows == 1){
for(int i=0; i<cols; i++){
if(sym[0][i] == 'X'){
printf("-1");
return 0;
}
ans += find_rots(sym[0][i],'E');
}
printf("%d",ans);
return 0;
}
ans = 2000999999;
if(rows == 3 && cols == 3){
for(int a=1; a<5; a++){
for(int b=1; b<5; b++){
for(int c=1; c<5; c++){
for(int d=1; d<5; d++){
for(int e=1; e<5; e++){
for(int f=1; f<5; f++){
for(int g=1; g<5; g++){
for(int h=1; h<5; h++){
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
visited[i][j] = false;
send[i][j] = 'X';
}
}
send[2][2] = 'F';
if(sym[0][0] != 'X') send[0][0] = ways[a];
if(sym[0][1] != 'X') send[0][1] = ways[b];
if(sym[0][2] != 'X') send[0][2] = ways[c];
if(sym[1][0] != 'X') send[1][0] = ways[d];
if(sym[1][1] != 'X') send[1][1] = ways[e];
if(sym[1][2] != 'X') send[1][2] = ways[f];
if(sym[2][0] != 'X') send[2][0] = ways[g];
if(sym[2][1] != 'X') send[2][1] = ways[h];
if(find_path(send)){
int temp = find_diff_rots(sym,send);
if(temp < ans) ans = temp;
}
}
}
}
}
}
}
}
}
if(ans == 2000999999) printf("-1");
}
if(m == 2) printf("-1");
}