USACO 2015 December Contest, Gold Problem 3. Bessie's Dream

But wait! Each tile has a color, and each color has a different property! Bessie's head hurts just thinking about it:

• If a tile is red, then it is impassable.
• If a tile is pink, then it can be walked on normally.
• If a tile is orange, then it can be walked on normally, but will make Bessie smell like oranges.
• If a tile is blue, then it contains piranhas that will only let Bessie pass if she smells like oranges.
• If a tile is purple, then Bessie will slide to the next tile in that direction (unless she is unable to cross it). If this tile is also a purple tile, then Bessie will continue to slide until she lands on a non-purple tile or hits an impassable tile. Sliding through a tile counts as a move. Purple tiles will also remove Bessie's smell.

(If you're confused about purple tiles, the example will illustrate their use.)

Please help Bessie get from the top-left to the bottom-right in as few moves as possible.

The next N

SAMPLE INPUT:

4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1

SAMPLE OUTPUT:

10

In this example, Bessie walks one square down and two squares to the right (and then slides one more square to the right). She walks one square up, one square left, and one square down (sliding two more squares down) and finishes by walking one more square right. This is a total of 10 moves (DRRRULDDDR).

Problem credits: Nathan Pinsker, inspired by the game "Undertale".

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
struct p{
	int x, y, s, l;
	friend bool operator <(p a, p b){
		return a.l > b.l;
	}
};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; 
	int n, m;
priority_queue<p> q;
int v[1005][1005][2]={0}, a[1005][1005];
void check(p t){
	if (t.x == n && t.y == m){
		cout<<t.l;
		exit(0);
	}
}
int main(){
	freopen("dream.in","r",stdin);
	freopen("dream.out","w", stdout);
	cin>>n>>m;
	for (int i = 1; i <= n; i++)
	    for (int j = 1; j <= m; j++)
	        scanf("%d", &a[i][j]);
    p h;
    for (int i = 1; i <= n;i ++) v[i][0][0] = v[i][0][1] = 1;
    for (int j = 1; j <= m; j++) v[0][j][0] = v[0][j][1] = 1;
    h.x = 1;h.y = 1;h.s = h.l = 0; v[1][1][0] = 1;
    q.push(h);
    while (!q.empty()){
    	h = q.top();
    
	//	cout<<h.x<<' '<<h.y<<"      "<<h.s<<"   "<<h.l<<endl;
    	q.pop();
    	for (int i = 0; i < 4; i++){
	    	p t = h;
	    	t.x += dx[i]; t.y += dy[i]; t.l++;
			if (!a[t.x][t.y] || v[t.x][t.y][t.s]) continue;
			if (a[t.x][t.y] == 1 || (a[t.x][t.y] == 3 && h.s)){
				check(t);
				q.push(t);
				v[t.x][t.y][t.s] = 1;
				continue;
			} 
			if (a[t.x][t.y] == 2){
				check(t);
				t.s = 1;
				v[t.x][t.y][t.s] = 1;
				q.push(t);
				continue;
			}
			if (a[t.x][t.y] == 4){
				int x = t.x - h.x;
				int y = t.y - h.y;
				t.s = 0; 
				//cout<<h.x<<' '<<h.y<<' '<<t.x<<' '<<t.y<<' ';
				while (t.x+x && t.y+y && t.x+x <= n && t.y+y <= m && a[t.x+x][t.y+y] && a[t.x+x][t.y+y] != 3){
					t.x += x;
					t.y += y;
					t.l++;
					if (a[t.x][t.y] != 4) break;
				}
				//cout<<t.x<<' '<<t.y<<endl;
				check(t);
				if (!v[t.x][t.y][t.s]){
					q.push(t);
					v[t.x][t.y][t.s] = 1;
				}
				
			}
	    }
    }
    cout<<"-1";
    return 0;
}