AC如惊鸿掠过(12pts,TLE + WA + AC求调 + 悬关)
查看原帖
AC如惊鸿掠过(12pts,TLE + WA + AC求调 + 悬关)
895690
gghack_Nythix楼主2023/7/19 15:01

rt

#include<bits/stdc++.h>
using namespace std;
int ans[600][600],dir[4][2] = {{-1,-1},{-1,1},{1,-1},{1,1}},gd[4][2] = {{0,0},{-1,0},{-1,-1},{0,-1}},ab[6] = {1,2,1,2},a[600][600];
struct node{
	int x,y;
}frt;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	memset(ans,0x3f,sizeof(ans));
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= m;++j){
			char x;
			cin >> x;
			if(x == '/'){
				a[i][j] = 1;
			}else{
				a[i][j] = 2;
			}
		}
	}
	deque<node>q;
	q.push_back(node{1,1});
	ans[1][1] = 0;
	while(!q.empty()){
		frt = q.front();q.pop_front();
		int wx = frt.x,wy = frt.y;
		for(int i = 0;i < 4;++i){
			int nx = wx + dir[i][0],ny = wy + dir[i][1],bx = wx + gd[i][0],by = wy + gd[i][1],wd = 0;
			wd = a[bx][by] != ab[i];
			if(nx <= n + 1 && nx >= 1 && ny >= 1 && ny <= m + 1 && ans[nx][ny] > ans[wx][wx] + wd){
				ans[nx][ny] = ans[wx][wy] + wd;
				//cout << nx << " " << ny << " " << ans[nx][ny] << endl;
				if(!wd){
					q.push_front(node{nx,ny});
				}else{
					q.push_back(node{nx,ny});
				}
				if(wx >= n + 1 && wy >= m + 1){
					break;
				}
			}
		}
	}
	if(ans[n][m] == 0x3f3f3f3f){
		cout << "NO SOLUTION" << endl;
		return 0;
	}
	cout << ans[n][m] << endl;
	return 0;
}
2023/7/19 15:01
加载中...