SSLOJ 1338. Escape Path

subject

Title Description

Unable to live in harmony with Garfield, Odie decided to escape. Unfortunately, he escaped to a rectangular lake. The lake is N in length and M in width, and Odie is in position (1,1) initially. Garfield wanted to know how many shortest paths Poor Odie had to reach (N, M) (not jump out of the lake boundary). In addition, the magic of Odie moves like a chess knight.
 

input

Two integers, N and M, denote the length and width of the lake.

output

An integer representing the number of shortest paths (module 9901 output).

Input sample replication

3 3

Output sample replication

2

Explain

For 50% of the data, N < 5,
For 100% data, N < 100.

 

Analysis

Direct shortest path? But record paths with open arrays

 

Code

 

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 int n,m;
 6 int vis[1001][1001],dis[1001][1001],ans[1001][1001];
 7 int fx[9][2]={{0,0},{1,2},{2,1},{-1,-2},{-2,-1},{1,-2},{-1,2},{-2,1},{2,-1}};
 8 void bfs()
 9 {
10     memset(dis,0x3f,sizeof(dis));
11     queue<int> q;
12     q.push(1); q.push(1); vis[1][1]=1; dis[1][1]=0; ans[1][1]=1;
13     while(!q.empty())
14     {
15         int x=q.front(); q.pop();
16         int y=q.front(); q.pop();
17         vis[x][y]=0;
18         for (int i=1;i<=8;i++)
19         {
20             int ax=x+fx[i][0],ay=y+fx[i][1];
21             if (ax<1||ay<1||ax>n||ay>m) continue;
22             if (dis[ax][ay]>dis[x][y]+1)
23             {
24                 dis[ax][ay]=dis[x][y]+1;
25                 if (!vis[ax][ay])
26                 {
27                    vis[ax][ay]=1;
28                    q.push(ax); q.push(ay);
29                 }
30                 ans[ax][ay]=ans[x][y];
31             }
32             else if (dis[ax][ay]==dis[x][y]+1)
33               ans[ax][ay]=(ans[x][y]+ans[ax][ay])%9901;
34         }
35     }
36 }
37 int main ()
38 {
39     cin>>n>>m;
40     bfs();
41     cout<<ans[n][m];
42 }

Tags: PHP

Posted on Tue, 08 Oct 2019 18:59:11 -0700 by offdarip