[USACO 2007 Feb B]Bronze Lilypad Pond

第1行: 四个空格分开的整数： M, N, M1, 和 M2
第2行至 M+1行: 第i+1行用N个空格分开的整数描述池塘第i行，0表示水，1表示荷叶，2表示岩石，3表示Bessie现在站的那块荷叶，4表示跳跃的终点。

C++14(g++5.4) 解法, 执行用时: 30ms, 内存消耗: 616K, 提交时间: 2020-02-13 13:23:19

#include<bits/stdc++.h>
using namespace std;

int m, n, m1, m2;
int maze[35][35];
int vis[35][35];
struct node{int x, y, step;};

int main() {
	node en;
	cin>>m>>n>>m1>>m2;
	queue <node> q;
	int dir[8][2] = {{-m1, m2}, {-m2, m1}, {m1, m2}, {m2, m1}, {m1, -m2}, {m2, -m1}, {-m1, -m2}, {-m2, -m1}};
	for(int i = 1; i <= m; i++) {
		 for(int j = 1; j <= n; j++) {
		 	cin>>maze[i][j];
		 	if(maze[i][j] == 3) {
				q.push({i, j, 0});
				vis[i][j] = 1;
			}
			else if(maze[i][j] == 4) {
				en.x = i;
				en.y = j;
			} 
		 }
	}
	while(!q.empty()) {
		node st = q.front(), ne;
		q.pop();
		if(st.x == en.x && st.y == en.y) {
			cout<<st.step<<endl;
			return 0;
		}
		for(int i = 0; i < 8; i++) {
			ne.x = st.x + dir[i][0];
			ne.y = st.y + dir[i][1];
			if(ne.x < 1 || ne.x > m || ne.y < 1 || ne.y > n || vis[ne.x][ne.y] || maze[ne.x][ne.y] == 0 || maze[ne.x][ne.y] == 2) continue;
			ne.step = st.step + 1;
			vis[ne.x][ne.y] = 1;
			q.push(ne);
			}
	}
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 504K, 提交时间: 2020-02-26 13:39:42

#include<stdio.h>
int qux[1000],quy[1000],head=0,tail=1;
int bd[30][30];
int main()
{
	int n,m,dx,dy;
	scanf("%d%d%d%d",&n,&m,&dx,&dy);
	int mx[8]={dx,dx,-dx,-dx,dy,dy,-dy,-dy};
	int my[8]={dy,-dy,dy,-dy,dx,-dx,dx,-dx};
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			int v;
			scanf("%d",&bd[i][j]);
			if(bd[i][j]==3)
			{
				qux[0]=i;
				quy[0]=j;
				bd[i][j]=100;
			}
		}
	}
	while(head!=tail)
	{
		for(int i=0;i<8;i++)
		{
			#define X qux[head]+mx[i]
			#define Y quy[head]+my[i]
			#define T bd[qux[head]][quy[head]]
			if(0<=X&&X<n&&0<=Y&&Y<m)
			{
				if(bd[X][Y]==4)
				{
					printf("%d",T-99);
					return 0;
				}
				if(bd[X][Y]==1)
				{
					bd[X][Y]=T+1;
					qux[tail]=X;
					quy[tail]=Y;
					tail++;
				}
			}
		}
		head++;
	}
}

详情