3 条题解
-
2
赵青海 (huhe) LV 7 SU @ 2021-8-7 21:05:13
C++ :
#include<iostream> #include<cstring> #include<cstdio> #include<stack> #include<queue> #define pii pair <int , int> //To simplify the questions, we prefer to use pair and make first -> x, second -> y. #define x first #define y second using namespace std; struct rec { int x, y, dir; } man, box, tg; //tg -> target const int MAX_size = 20 + 10; const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; const char cdir[5] = {'N', 'S', 'W', 'E', '\0'}, ddir[5] = {'n', 's', 'w', 'e', '\0'}; //up 0 down 1 left 2 right 3 queue <char> ans; bool book[MAX_size][MAX_size][4]; bool mat[MAX_size][MAX_size]; char map[MAX_size][MAX_size]; int n, m; int d[MAX_size][MAX_size], d_man[MAX_size][MAX_size][4], f_box[MAX_size][MAX_size][4], d_box[MAX_size][MAX_size][4]; int f_man[MAX_size][MAX_size]; void init() { memset(f_man, -1, sizeof(f_man)); memset(f_box, -1, sizeof(f_box)); memset(d_man, -1, sizeof(d_man)); memset(d_box, -1, sizeof(d_box)); memset(mat, false, sizeof(mat)); memset(book, false, sizeof(book)); for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= m; ++ j) { if(map[i][j] == 'S')man.x = i, man.y = j; else if(map[i][j] == 'B')box.x = i, box.y = j; else if(map[i][j] == 'T')tg.x = i, tg.y = j, tg.dir = -1; } } return; } bool valid(int x, int y) { if(x < 1 || x > n || y < 1 || y > m || map[x][y] == '#') return 0; return 1; } int expand(pii st, pii ed, stack <char> &s) { queue <pii> Q; while(!s.empty()) s.pop(); while(!Q.empty()) Q.pop(); if(st.x == ed.x && st.y == ed.y) return 0; Q.push(st); mat[st.x][st.y] = true; d[st.x][st.y] = 0; while(!Q.empty()) { pii now = Q.front(), next; Q.pop(); for(int k = 0; k < 4; ++ k) { next = make_pair(now.x + dx[k], now.y + dy[k]); if(!valid(next.x, next.y) || mat[next.x][next.y]) continue; f_man[next.x][next.y] = k; mat[next.x][next.y] = true; d[next.x][next.y] = d[now.x][now.y] + 1; if(next.x == ed.x && next.y == ed.y) { int prev_x = next.x, prev_y = next.y, tmp_1, tmp_2; while(!(prev_x == st.x && prev_y == st.y)) { s.push(ddir[f_man[prev_x][prev_y]]); tmp_1 = prev_x - dx[f_man[prev_x][prev_y]]; tmp_2 = prev_y - dy[f_man[prev_x][prev_y]]; prev_x = tmp_1, prev_y = tmp_2; } return d[next.x][next.y]; } Q.push(next); } } return -1; } void _print(int x, int y, int dir) { stack <char> s; if(x == box.x && y == box.y && f_box[x][y][dir] == -1) { mat[box.x][box.y] = true; expand(make_pair(man.x, man.y), make_pair(box.x - dx[dir], box.y - dy[dir]), s); memset(mat, false, sizeof(mat)); while(!s.empty()) { ans.push(s.top()); s.pop(); } return; } int prev_dir = f_box[x][y][dir], prev_x = x - (dx[dir] + dx[prev_dir]), prev_y = y - dy[dir] - dy[prev_dir]; _print(x - dx[dir], y - dy[dir], prev_dir); mat[x - dx[dir]][y - dy[dir]] = true; expand(make_pair(prev_x, prev_y), make_pair(x - (dx[dir] * 2), y - (dy[dir] * 2)), s); memset(mat, false, sizeof(mat)); while(!s.empty()) { ans.push(s.top()); s.pop(); } ans.push(cdir[dir]); return; } bool bfs() { queue <rec> Q; stack <char> s; while(!Q.empty()) Q.pop(); int k; for(k = 0; k < 4; ++ k) { int &num = d_box[box.x][box.y][k], &cnt = d_man[box.x][box.y][k]; if(!valid(box.x - dx[k], box.y - dy[k])) continue; mat[box.x][box.y] = true; cnt = expand(make_pair(man.x, man.y), make_pair(box.x - dx[k], box.y - dy[k]), s); memset(mat, false, sizeof(mat)); if(cnt == -1) continue; Q.push(rec {box.x, box.y, k}); book[box.x][box.y][k] = true; num = 0; } while(!Q.empty()) { rec now = Q.front(), next; Q.pop(); for(k = 0; k < 4; ++ k) { next.x = now.x + dx[k]; next.y = now.y + dy[k]; next.dir = k; if(!valid(next.x, next.y)) continue; int &num = d_box[next.x][next.y][k], &cnt = d_man[next.x][next.y][k] , tmp; mat[now.x][now.y] = true; tmp = expand(make_pair(now.x - dx[now.dir], now.y - dy[now.dir]), make_pair(now.x - dx[k], now.y - dy[k]), s); memset(mat, false, sizeof(mat)); if(tmp == -1) continue; if(book[next.x][next.y][next.dir]) { if(num >= d_box[now.x][now.y][now.dir] + 1 && cnt > tmp + d_man[now.x][now.y][now.dir]) { num = d_box[now.x][now.y][now.dir] + 1; cnt = d_man[now.x][now.y][now.dir] + tmp; f_box[next.x][next.y][k] = now.dir; } continue; } book[next.x][next.y][k] = true; f_box[next.x][next.y][next.dir] = now.dir; num = d_box[now.x][now.y][now.dir] + 1; cnt = d_man[now.x][now.y][now.dir] + tmp; if(next.x == tg.x && next.y == tg.y) { if(tg.dir == -1) tg.dir = next.dir; else { if(num > d_box[tg.x][tg.y][tg.dir]) { _print(tg.x, tg.y, tg.dir); return true; } else if(cnt < d_man[tg.x][tg.y][tg.dir]) tg.dir = next.dir; } } Q.push(next); } } if(tg.dir != -1) { _print(tg.x, tg.y, tg.dir); return true; } return false; } int main() { int T = 1; while(scanf("%d %d", &n, &m) == 2 && n && m) { printf("Maze #%d\n", (T ++)); for(int i = 1; i <= n; ++ i) { scanf("%s", map[i] + 1); } init(); if(bfs()) { while(!ans.empty()) { printf("%c", ans.front()); ans.pop(); } puts(""); } else puts("Impossible."); puts(""); } return 0; } -
0
#include<iostream> #include<cstring> #include<cstdio> #include<stack> #include<queue> #define pii pair <int , int> //To simplify the questions, we prefer to use pair and make first -> x, second -> y. #define x first #define y second using namespace std; struct rec { int x, y, dir; } man, box, tg; //tg -> target const int MAX_size = 20 + 10; const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; const char cdir[5] = {'N', 'S', 'W', 'E', '\0'}, ddir[5] = {'n', 's', 'w', 'e', '\0'}; //up 0 down 1 left 2 right 3 queue <char> ans; bool book[MAX_size][MAX_size][4]; bool mat[MAX_size][MAX_size]; char map[MAX_size][MAX_size]; int n, m; int d[MAX_size][MAX_size], d_man[MAX_size][MAX_size][4], f_box[MAX_size][MAX_size][4], d_box[MAX_size][MAX_size][4]; int f_man[MAX_size][MAX_size]; void init() { memset(f_man, -1, sizeof(f_man)); memset(f_box, -1, sizeof(f_box)); memset(d_man, -1, sizeof(d_man)); memset(d_box, -1, sizeof(d_box)); memset(mat, false, sizeof(mat)); memset(book, false, sizeof(book)); for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= m; ++ j) { if(map[i][j] == 'S')man.x = i, man.y = j; else if(map[i][j] == 'B')box.x = i, box.y = j; else if(map[i][j] == 'T')tg.x = i, tg.y = j, tg.dir = -1; } } return; }
bool valid(int x, int y) { if(x < 1 || x > n || y < 1 || y > m || map[x][y] == '#') return 0; return 1; }
int expand(pii st, pii ed, stack <char> &s) { queue <pii> Q; while(!s.empty()) s.pop(); while(!Q.empty()) Q.pop(); if(st.x == ed.x && st.y == ed.y) return 0; Q.push(st); mat[st.x][st.y] = true; d[st.x][st.y] = 0; while(!Q.empty()) { pii now = Q.front(), next; Q.pop(); for(int k = 0; k < 4; ++ k) { next = make_pair(now.x + dx[k], now.y + dy[k]);
if(!valid(next.x, next.y) || mat[next.x][next.y]) continue; f_man[next.x][next.y] = k; mat[next.x][next.y] = true; d[next.x][next.y] = d[now.x][now.y] + 1; if(next.x == ed.x && next.y == ed.y) { int prev_x = next.x, prev_y = next.y, tmp_1, tmp_2; while(!(prev_x == st.x && prev_y == st.y)) { s.push(ddir[f_man[prev_x][prev_y]]); tmp_1 = prev_x - dx[f_man[prev_x][prev_y]]; tmp_2 = prev_y - dy[f_man[prev_x][prev_y]]; prev_x = tmp_1, prev_y = tmp_2; } return d[next.x][next.y]; } Q.push(next); } } return -1;}
void _print(int x, int y, int dir) { stack <char> s; if(x == box.x && y == box.y && f_box[x][y][dir] == -1) { mat[box.x][box.y] = true; expand(make_pair(man.x, man.y), make_pair(box.x - dx[dir], box.y - dy[dir]), s); memset(mat, false, sizeof(mat)); while(!s.empty()) { ans.push(s.top()); s.pop(); } return; } int prev_dir = f_box[x][y][dir], prev_x = x - (dx[dir] + dx[prev_dir]), prev_y = y - dy[dir] - dy[prev_dir]; _print(x - dx[dir], y - dy[dir], prev_dir); mat[x - dx[dir]][y - dy[dir]] = true; expand(make_pair(prev_x, prev_y), make_pair(x - (dx[dir] * 2), y - (dy[dir] * 2)), s); memset(mat, false, sizeof(mat)); while(!s.empty()) { ans.push(s.top()); s.pop(); } ans.push(cdir[dir]); return; }
bool bfs() { queue <rec> Q; stack <char> s; while(!Q.empty()) Q.pop(); int k; for(k = 0; k < 4; ++ k) { int &num = d_box[box.x][box.y][k], &cnt = d_man[box.x][box.y][k]; if(!valid(box.x - dx[k], box.y - dy[k])) continue; mat[box.x][box.y] = true; cnt = expand(make_pair(man.x, man.y), make_pair(box.x - dx[k], box.y - dy[k]), s); memset(mat, false, sizeof(mat)); if(cnt == -1) continue; Q.push(rec {box.x, box.y, k}); book[box.x][box.y][k] = true; num = 0; } while(!Q.empty()) { rec now = Q.front(), next; Q.pop(); for(k = 0; k < 4; ++ k) { next.x = now.x + dx[k]; next.y = now.y + dy[k]; next.dir = k; if(!valid(next.x, next.y)) continue; int &num = d_box[next.x][next.y][k], &cnt = d_man[next.x][next.y][k] , tmp; mat[now.x][now.y] = true; tmp = expand(make_pair(now.x - dx[now.dir], now.y - dy[now.dir]), make_pair(now.x - dx[k], now.y - dy[k]), s); memset(mat, false, sizeof(mat)); if(tmp == -1) continue; if(book[next.x][next.y][next.dir]) { if(num >= d_box[now.x][now.y][now.dir] + 1 && cnt > tmp + d_man[now.x][now.y][now.dir]) { num = d_box[now.x][now.y][now.dir] + 1; cnt = d_man[now.x][now.y][now.dir] + tmp; f_box[next.x][next.y][k] = now.dir; } continue; } book[next.x][next.y][k] = true; f_box[next.x][next.y][next.dir] = now.dir; num = d_box[now.x][now.y][now.dir] + 1; cnt = d_man[now.x][now.y][now.dir] + tmp; if(next.x == tg.x && next.y == tg.y) { if(tg.dir == -1) tg.dir = next.dir; else { if(num > d_box[tg.x][tg.y][tg.dir]) { _print(tg.x, tg.y, tg.dir); return true; } else if(cnt < d_man[tg.x][tg.y][tg.dir]) tg.dir = next.dir; } } Q.push(next); } } if(tg.dir != -1) { _print(tg.x, tg.y, tg.dir); return true; } return false; }
int main() { int T = 1; while(scanf("%d %d", &n, &m) == 2 && n && m) { printf("Maze #%d\n", (T ++)); for(int i = 1; i <= n; ++ i) { scanf("%s", map[i] + 1); } init(); if(bfs()) { while(!ans.empty()) { printf("%c", ans.front()); ans.pop(); } puts(""); } else puts("Impossible."); puts(""); } return 0; }
-
0
#include<iostream> #include<cstring> #include<cstdio> #include<stack> #include<queue> #define pii pair <int , int> //To simplify the questions, we prefer to use pair and make first -> x, second -> y. #define x first #define y second using namespace std; struct rec { int x, y, dir; } man, box, tg; //tg -> target const int MAX_size = 20 + 10; const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; const char cdir[5] = {'N', 'S', 'W', 'E', '\0'}, ddir[5] = {'n', 's', 'w', 'e', '\0'}; //up 0 down 1 left 2 right 3 queue <char> ans; bool book[MAX_size][MAX_size][4]; bool mat[MAX_size][MAX_size]; char map[MAX_size][MAX_size]; int n, m; int d[MAX_size][MAX_size], d_man[MAX_size][MAX_size][4], f_box[MAX_size][MAX_size][4], d_box[MAX_size][MAX_size][4]; int f_man[MAX_size][MAX_size]; void init() { memset(f_man, -1, sizeof(f_man)); memset(f_box, -1, sizeof(f_box)); memset(d_man, -1, sizeof(d_man)); memset(d_box, -1, sizeof(d_box)); memset(mat, false, sizeof(mat)); memset(book, false, sizeof(book)); for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= m; ++ j) { if(map[i][j] == 'S')man.x = i, man.y = j; else if(map[i][j] == 'B')box.x = i, box.y = j; else if(map[i][j] == 'T')tg.x = i, tg.y = j, tg.dir = -1; } } return; }
bool valid(int x, int y) { if(x < 1 || x > n || y < 1 || y > m || map[x][y] == '#') return 0; return 1; }
int expand(pii st, pii ed, stack <char> &s) { queue <pii> Q; while(!s.empty()) s.pop(); while(!Q.empty()) Q.pop(); if(st.x == ed.x && st.y == ed.y) return 0; Q.push(st); mat[st.x][st.y] = true; d[st.x][st.y] = 0; while(!Q.empty()) { pii now = Q.front(), next; Q.pop(); for(int k = 0; k < 4; ++ k) { next = make_pair(now.x + dx[k], now.y + dy[k]);
if(!valid(next.x, next.y) || mat[next.x][next.y]) continue; f_man[next.x][next.y] = k; mat[next.x][next.y] = true; d[next.x][next.y] = d[now.x][now.y] + 1; if(next.x == ed.x && next.y == ed.y) { int prev_x = next.x, prev_y = next.y, tmp_1, tmp_2; while(!(prev_x == st.x && prev_y == st.y)) { s.push(ddir[f_man[prev_x][prev_y]]); tmp_1 = prev_x - dx[f_man[prev_x][prev_y]]; tmp_2 = prev_y - dy[f_man[prev_x][prev_y]]; prev_x = tmp_1, prev_y = tmp_2; } return d[next.x][next.y]; } Q.push(next); } } return -1;}
void _print(int x, int y, int dir) { stack <char> s; if(x == box.x && y == box.y && f_box[x][y][dir] == -1) { mat[box.x][box.y] = true; expand(make_pair(man.x, man.y), make_pair(box.x - dx[dir], box.y - dy[dir]), s); memset(mat, false, sizeof(mat)); while(!s.empty()) { ans.push(s.top()); s.pop(); } return; } int prev_dir = f_box[x][y][dir], prev_x = x - (dx[dir] + dx[prev_dir]), prev_y = y - dy[dir] - dy[prev_dir]; _print(x - dx[dir], y - dy[dir], prev_dir); mat[x - dx[dir]][y - dy[dir]] = true; expand(make_pair(prev_x, prev_y), make_pair(x - (dx[dir] * 2), y - (dy[dir] * 2)), s); memset(mat, false, sizeof(mat)); while(!s.empty()) { ans.push(s.top()); s.pop(); } ans.push(cdir[dir]); return; }
bool bfs() { queue <rec> Q; stack <char> s; while(!Q.empty()) Q.pop(); int k; for(k = 0; k < 4; ++ k) { int &num = d_box[box.x][box.y][k], &cnt = d_man[box.x][box.y][k]; if(!valid(box.x - dx[k], box.y - dy[k])) continue; mat[box.x][box.y] = true; cnt = expand(make_pair(man.x, man.y), make_pair(box.x - dx[k], box.y - dy[k]), s); memset(mat, false, sizeof(mat)); if(cnt == -1) continue; Q.push(rec {box.x, box.y, k}); book[box.x][box.y][k] = true; num = 0; } while(!Q.empty()) { rec now = Q.front(), next; Q.pop(); for(k = 0; k < 4; ++ k) { next.x = now.x + dx[k]; next.y = now.y + dy[k]; next.dir = k; if(!valid(next.x, next.y)) continue; int &num = d_box[next.x][next.y][k], &cnt = d_man[next.x][next.y][k] , tmp; mat[now.x][now.y] = true; tmp = expand(make_pair(now.x - dx[now.dir], now.y - dy[now.dir]), make_pair(now.x - dx[k], now.y - dy[k]), s); memset(mat, false, sizeof(mat)); if(tmp == -1) continue; if(book[next.x][next.y][next.dir]) { if(num >= d_box[now.x][now.y][now.dir] + 1 && cnt > tmp + d_man[now.x][now.y][now.dir]) { num = d_box[now.x][now.y][now.dir] + 1; cnt = d_man[now.x][now.y][now.dir] + tmp; f_box[next.x][next.y][k] = now.dir; } continue; } book[next.x][next.y][k] = true; f_box[next.x][next.y][next.dir] = now.dir; num = d_box[now.x][now.y][now.dir] + 1; cnt = d_man[now.x][now.y][now.dir] + tmp; if(next.x == tg.x && next.y == tg.y) { if(tg.dir == -1) tg.dir = next.dir; else { if(num > d_box[tg.x][tg.y][tg.dir]) { _print(tg.x, tg.y, tg.dir); return true; } else if(cnt < d_man[tg.x][tg.y][tg.dir]) tg.dir = next.dir; } } Q.push(next); } } if(tg.dir != -1) { _print(tg.x, tg.y, tg.dir); return true; } return false; }
int main() { int T = 1; while(scanf("%d %d", &n, &m) == 2 && n && m) { printf("Maze #%d\n", (T ++)); for(int i = 1; i <= n; ++ i) { scanf("%s", map[i] + 1); } init(); if(bfs()) { while(!ans.empty()) { printf("%c", ans.front()); ans.pop(); } puts(""); } else puts("Impossible."); puts(""); } return 0; }
- 1
信息
- ID
- 85
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 32
- 已通过
- 27
- 上传者
-