SERGRID.cpp

#include <iostream>
using namespace std;

const int MAX = 505;
const int MAX_QUEUE = MAX*MAX;

int n, m;               // Kích thước ma trận
int Matrix[MAX][MAX];   // Ma trận ban đầu
int Mark[MAX][MAX];     // Ma trận đánh dấu

typedef struct
{
	int row;
	int col;
}Point;

// Hàng đợi vòng
Point queue[MAX_QUEUE];
int fr, re, leng;

void Enqueue(int row, int col)
{
	Point p;
	p.row = row;
	p.col = col;

	queue[re] = p;
	re = (re + 1) % MAX_QUEUE;
	leng++;
}

Point Dequeue()
{
	Point p = queue[fr];
	fr =  (fr + 1) % MAX_QUEUE;
	leng--;
	return p;
}

int drow[] = {-1,0,1, 0};
int dcol[] = { 0,1,0,-1};

/*
* Thuật toán BFS từ điểm đầu tiên (sr, sc)
*/
void BFS(int sr, int sc)
{
	fr = re = leng = 0;
	Mark[sr][sc] = 1;
	Enqueue(sr,sc);

	while(leng > 0)
	{
		Point p = Dequeue();
		for(int i = 0; i < 4; i++)
		{
			int r = p.row + (drow[i]) * Matrix[p.row][p.col];
			int c = p.col + (dcol[i]) * Matrix[p.row][p.col];
			if( r >= 0 && r < n && c >= 0 && c < m && 
			    (Mark[r][c] == 0 || Mark[r][c] > Mark[p.row][p.col] + 1)
			    )
			{
				Mark[r][c] = Mark[p.row][p.col] + 1;
				Enqueue(r,c);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		char tmp[MAX];
		cin >> tmp;
		for(int j = 0; j < m; j++)
		{
			Matrix[i][j] = tmp[j] - '0';
			Mark[i][j]   = 0;
		}
	}

	BFS(0,0);
	
	// Nếu giá trị ô cuối cùng vẫn bằng 0, nghĩa là nó được thăm
	if(Mark[n-1][m-1] == 0) cout << -1 << endl;
	else cout << Mark[n-1][m-1] - 1 << endl;
	return 0;
}