90pts WA #8
查看原帖
90pts WA #8
744562
Aya_tt楼主2024/6/25 11:23
#include<bits/stdc++.h>
using namespace std;
int n, m;
bool mp1[60][60], mp[60][60], vis[60][60][5];
int dis[60][60][5];
struct aaa{
	int x, y, z;
};
queue<aaa> q;
int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cin >> mp1[i][j];
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(mp1[i][j] == 1) {
				mp[i][j] = 1;
				mp[i - 1][j - 1] = 1;
				mp[i][j - 1] = 1;
				mp[i - 1][j] = 1;
			}
		}
	}
/*	cout << endl;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			cout << mp[i][j] << " ";
		}
		cout << endl;
	}*/
	int a, b, A, B;
	char c;
	cin >> a >> b >> A >> B >> c;
	int o;
	if(c == 'N') {
		o = 1;
	}
	if(c == 'E') {
		o = 2;
	}
	if(c == 'S') {
		o = 3;
	}
	if(c == 'W') {
		o = 4;
	}
    vis[a][b][o] = 1;
    aaa r;
    r.x = a, r.y = b, r.z = o;
    q.push(r);
    dis[a][b][o] = 0;
    while(!q.empty()){
    	aaa p = q.front();
    	q.pop();
    	int x = p.x, y = p.y, z = p.z;
    	//cout << x << " " << y << " " << z << " " << dis[x][y][z] << endl;
    	if(x == A && y == B) {
    		cout << dis[A][B][z];
    		return 0;
		}
    	int xx = x, yy = y, zz = z;
    	for(int i = 1;i <= 3;i++){
    		if(z == 1) {
    			x--;
    			if(mp[x][y] == 1) {
    				break;
				}
			} 
			if(z == 2) {
				y++;
				if(mp[x][y] == 1) {
    				break;
				}
			}
			if(z == 3) {
				x++;
				if(mp[x][y] == 1) {
    				break;
				}
			}
			if(z == 4) {
				y--;
				if(mp[x][y] == 1) {
    				break;
				}
			}
			if(x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] == 0 && !vis[x][y][z]) {
				aaa k;
				k.x = x, k.y = y, k.z = z;
				dis[x][y][z] = dis[xx][yy][zz] + 1;
				vis[x][y][z] = 1;
				q.push(k);
			}
		}
		if(z == 1) {
			if(!vis[xx][yy][4]) {
				aaa k;
				k.x = xx, k.y = yy, k.z = 4;
				q.push(k);
				vis[xx][yy][k.z] = 1;
				dis[xx][yy][4] = dis[xx][yy][1] + 1;	
			}
			if(!vis[xx][yy][2]) {
				aaa k;
				k.x = xx, k.y = yy, k.z = 2;
				q.push(k);
				vis[xx][yy][k.z] = 1;
				dis[xx][yy][2] = dis[xx][yy][1] + 1;	
			}
		}
		else if(z == 4) {
			if(!vis[xx][yy][1]) {
				aaa k;
				k.x = xx, k.y = yy, k.z = 1;
				q.push(k);
				vis[xx][yy][k.z] = 1;
				dis[xx][yy][1] = dis[xx][yy][4] + 1;	
			}
			if(!vis[xx][yy][3]) {
				aaa k;
				k.x = xx, k.y = yy, k.z = 3;
				q.push(k);
				vis[xx][yy][k.z] = 1;
				dis[xx][yy][3] = dis[xx][yy][4] + 1;	
			}
		}
		else {
			if(!vis[xx][yy][z + 1]) {
				aaa k;
				k.x = xx, k.y = yy, k.z = z + 1;
				q.push(k);
				vis[xx][yy][k.z] = 1;
				dis[xx][yy][z + 1] = dis[xx][yy][z] + 1;	
			}
			if(!vis[xx][yy][z - 1]) {
				aaa k;
				k.x = xx, k.y = yy, k.z = z - 1;
				q.push(k);
				vis[xx][yy][k.z] = 1;
				dis[xx][yy][z - 1] = dis[xx][yy][z] + 1;	
			}
		}
	}
	cout << -1;
}
2024/6/25 11:23
加载中...