社区讨论
求问E题hack以及思路为何错误
学术版参与者 4已保存回复 14
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 14 条
- 当前快照
- 1 份
- 快照标识符
- @mhj23f3h
- 此快照首次捕获于
- 2025/11/03 19:28 4 个月前
- 此快照最后确认于
- 2025/11/03 20:37 4 个月前
rt,我的思路比较猎奇,就是会被弄脏当且仅当他的正上/下/左/右,有垃圾出现,这时移动相反方向会出现垃圾,那么你枚举上下左右移动的顺序,然后模拟能往这个方向移动就移动的过程。
CPP# include <bits/stdc++.h>
using namespace std ;
constexpr int N = 50 ;
int n , m , s , t , ord[N] , shang , xia , zuo , you , ans = 1000000000 ;
char a[N][N] , mp[N][N] , cmp[N][N] ;
void update () {
shang = 0 , xia = n + 1 , zuo = 0 , you = m + 1 ;
for ( int i = 1;i < s;++i ) if ( cmp[i][t] == '#' ) shang = i ;
for ( int i = s + 1;i <= n;++i ) if ( cmp[i][t] == '#' ) xia = i ;
for ( int i = 1;i < t;++i ) if ( cmp[s][i] == '#' ) zuo = i ;
for ( int i = t + 1;i <= m;++i ) if ( cmp[s][i] == '#' ) you = i ;
return ;
}
char modify ( int x , int y ) {
if ( x < 1 || x > n || y < 1 || y > m ) return '.' ;
return cmp[x][y] ;
}
bool check ( int x , int y ) {
if ( x < 1 || x > n || y < 1 || y > m ) return 0 ;
return cmp[x][y] == '#' ;
}
signed main () {
cin >> n >> m ;
for ( int i = 0;i <= 30;++i ) for ( int j = 0;j <= 30;++j ) a[i][j] = '.' ;
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j ) {
cin >> a[i][j] ;
if ( a[i][j] == 'T' ) s = i , t = j ;
}
for ( int i = 1;i <= 4;++i ) ord[i] = i ;
do {
int cnt = 0 ;
for ( int i = 0;i <= 30;++i ) for ( int j = 0;j <= 30;++j ) cmp[i][j] = '.' ;
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j ) cmp[i][j] = a[i][j] ;
for ( int sb = 1;sb <= 4;++sb ) {
update () ;
// cout << shang << " " << xia << " " << zuo << " " << you << '\n' ;
if ( ord[sb] == 1 ) {
if ( xia == n + 1 ) {
int cc = 0 ;
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j ) if ( cmp[i][j] == '#' ) cc = max ( cc , i ) ;
cnt += cc ;
for ( int i = 0;i <= 30;++i ) for ( int j = 0;j <= 30;++j ) cmp[i][j] = '.' ;
goto shabi ;
}
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j )
if ( ( i != s || j != t ) && check ( i + ( xia - s - 1 ) , j ) ) mp[i][j] = modify ( i + ( xia - s - 1 ) , j ) ;
else if ( i == s && j == t ) mp[i][j] = 'T' ;
else mp[i][j] = '.' ;
cnt += ( xia - s - 1 ) ;
}
if ( ord[sb] == 2 ) {
if ( shang == 0 ) {
int cc = 114514 ;
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j ) if ( cmp[i][j] == '#' ) cc = min ( cc , i ) ;
cnt += n - cc + 1 ;
for ( int i = 0;i <= 30;++i ) for ( int j = 0;j <= 30;++j ) cmp[i][j] = '.' ;
goto shabi ;
}
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j )
if ( ( i != s || j != t ) && check ( i - ( s - shang - 1 ) , j ) ) mp[i][j] = modify ( i - ( s - shang - 1 ) , j ) ;
else if ( i == s && j == t ) mp[i][j] = 'T' ;
else mp[i][j] = '.' ;
cnt += ( s - shang - 1 ) ;
}
if ( ord[sb] == 3 ) {
if ( you == m + 1 ) {
int cc = 0 ;
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j ) if ( cmp[i][j] == '#' ) cc = max ( cc , j ) ;
cnt += cc ;
for ( int i = 0;i <= 30;++i ) for ( int j = 0;j <= 30;++j ) cmp[i][j] = '.' ;
goto shabi ;
}
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j )
if ( ( i != s || j != t ) && check ( i , j + ( you - t - 1 ) ) ) mp[i][j] = modify ( i , j + ( you - t - 1 ) ) ;
else if ( i == s && j == t ) mp[i][j] = 'T' ;
else mp[i][j] = '.' ;
cnt += ( you - t - 1 ) ;
}
if ( ord[sb] == 4 ) {
if ( zuo == 0 ) {
// cout << sb << '\n' ;
int cc = 0 ;
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j ) if ( cmp[i][j] == '#' ) cc = min ( cc , j ) ;
cnt += m - cc + 1 ;
for ( int i = 0;i <= 30;++i ) for ( int j = 0;j <= 30;++j ) cmp[i][j] = '.' ;
goto shabi ;
}
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j )
if ( ( i != s || j != t ) && check ( i , j - ( t - zuo - 1 ) ) ) mp[i][j] = modify ( i , j - ( t - zuo - 1 ) ) ;
else if ( i == s && j == t ) mp[i][j] = 'T' ;
else mp[i][j] = '.' ;
cnt += ( t - zuo - 1 ) ;
}
for ( int i = 0;i <= 30;++i ) for ( int j = 0;j <= 30;++j ) cmp[i][j] = '.' ;
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j ) cmp[i][j] = mp[i][j] ;
for ( int i = 0;i <= 30;++i ) for ( int j = 0;j <= 30;++j ) mp[i][j] = '.' ;
// for ( int i = 1;i <= n;++i ) { for ( int j = 1;j <= m;++j ) cout << cmp[i][j] ; cout << '\n' ; }
}
shabi : ;
bool flag = 1 ;
for ( int i = 1;i <= n;++i ) for ( int j = 1;j <= m;++j ) if ( cmp[i][j] == '#' ) { flag = 0 ; break ; }
if ( flag ) {
ans = min ( ans , cnt ) ;
// for ( int i = 1;i <= 4;++i ) cout << ord[i] << " " ;
// cout << cnt << '\n' ;
}
} while ( next_permutation ( ord + 1 , ord + 5 ) ) ;
if ( ans == 1000000000 ) cout << "-1\n" ;
else cout << ans << '\n' ;
return 0 ;
}
回复
共 14 条回复,欢迎继续交流。
正在加载回复...