社区讨论

求问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 条回复,欢迎继续交流。

正在加载回复...