Codeforces Problem 710A King Moves

Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 256 megabytes

Problem Description

The only king stands on the standard chess board. You are given his position in format "cd", where c is the column from 'a' to 'h' and d is the row from '1' to '8'. Find the number of moves permitted for the king.

Check the king's moves here https://en.wikipedia.org/wiki/King_(chess).

King moves from the position e4

Input

The only line contains the king's position in the format "cd", where 'c' is the column from 'a' to 'h' and 'd' is the row from '1' to '8'.

Output

Print the only integer x — the number of moves permitted for the king.

Sample Input

e4

Sample Output

8

Hint

Problem Idea

解题思路:

【题意】
在8*8的棋盘上放有一颗棋子(国王)

它可以朝相邻的8个格子移动一步,如图'×'就是棋子能移动的位置,当然,棋子不能移出棋盘

现在给你棋子的列与行,问棋子运行移动的位置有几个

【类型】
implementation

【分析】

其实,棋子能移动的位置取决于棋子当前所在位置

比如,如果棋子在最角落,那么只有3个位置可以移动

如果棋子在棋盘边上,则有5个位置可以移动

其他位置的话,则有8个位置可以移动

当然,本人不采取分类讨论的方法

由图中可以看出,求棋子能够移动的位置数,其实可以转化为求矩形内的格子数-1

而要求矩形内的格子数,只需要知道矩形右上角格子的坐标和左下角格子的坐标就可以了

假设,我们将棋盘行列编号均设为0~7,当前国王所在位置为(r,c)

那么矩形的右上角格子坐标为(min(r+1,7),min(c+1,7)),右下角格子坐标为(max(r-1,0),max(c-1,0))

这里用到max,min是防止棋子移出棋盘

【时间复杂度&&优化】
O(1)

题目链接→Codeforces Problem 710A King Moves

Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 1005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
char s[5];
int main()
{int r,c;scanf("%s",s);c=s[0]-'a';r=s[1]-'1';printf("%d\n",(min(7,r+1)-max(0,r-1)+1)*(min(7,c+1)-max(0,c-1)+1)-1);return 0;
}

菜鸟成长记

Codeforces Problem 710A King Moves(implementation)