War Chess
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2929 Accepted Submission(s): 733
Problem Description War chess is hh's favorite game:
In this game, there is an N * M battle map, and every player has his own Moving Val (MV). In each round, every player can move in four directions as long as he has enough MV. To simplify the problem, you are given your position and asked to output which grids you can arrive.
In the map:
'Y' is your current position (there is one and only one Y in the given map).
'.' is a normal grid. It costs you 1 MV to enter in this gird.
'T' is a tree. It costs you 2 MV to enter in this gird.
'R' is a river. It costs you 3 MV to enter in this gird.
'#' is an obstacle. You can never enter in this gird.
'E's are your enemies. You cannot move across your enemy, because once you enter the grids which are adjacent with 'E', you will lose all your MV. Here “adjacent” means two grids share a common edge.
'P's are your partners. You can move across your partner, but you cannot stay in the same grid with him final, because there can only be one person in one grid.You can assume the Ps must stand on '.' . so ,it also costs you 1 MV to enter this grid.
Input The first line of the inputs is T, which stands for the number of test cases you need to solve.
Then T cases follow:
Each test case starts with a line contains three numbers N,M and MV (2<= N , M <=100,0<=MV<= 65536) which indicate the size of the map and Y's MV.Then a N*M two-dimensional array follows, which describe the whole map.
Output Output the N*M map, using '*'s to replace all the grids 'Y' can arrive (except the 'Y' grid itself). Output a blank line after each case.
Sample Input
5
3 3 100
...
.E.
..Y
5 6 4
......
....PR
..E.PY
...ETT
....TT
2 2 100
.E
EY
5 5 2
.....
..P..
.PYP.
..P..
.....
3 3 1
.E.
EYE
...
Sample Output
...
.E*
.*Y
...***
..**P*
..E*PY
...E**
....T*
.E
EY
..*..
.*P*.
*PYP*
.*P*.
..*..
.E.
EYE
.*.
這題不是坑點挺多的，而是需要的優化的地方蠻多的。網上大部分都是直接用優先隊列做的，其實上來就去思考優先隊列的精妙之處确實并不是那麼簡單，我先寫了一個普通隊列版本的（當然可以AC），裡面包含了所有優先隊列所能優化的點，可以先看一下，具體内容代碼裡說。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
typedef long long ll;
char map[105][105];//原始圖
char omap[105][105];//記錄*的圖
int n,m,sum;
int book[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};//四個方位
int vis[105][105];//記錄每個點所剩最大mv值
int flag[105][105];//記錄那些根本不需要走的點
int num[105][105];//記錄在隊列裡面有幾個這個點的元素并試試更新（不懂往後看）
typedef struct
{
int x;
int y;
} node;
bool enemy(int x,int y)//判斷周圍有沒有E
{
int j;
for(j = 0;j< 4;j++)
{
int txx = x+book[j][0];
int tyy = y+book[j][1];
if(map[txx][tyy] == 'E')
{
flag[x][y] = 1;
break;
}
}
if(j == 4)
return 1;
else
return 0;
}
queue<node> q;//申請隊列
void bfs(int sx,int sy)
{
node s;
s.x = sx;
s.y = sy;
q.push(s);
vis[sx][sy] = sum;//初始點的mv值是全部的mv
num[sx][sy] = 1;//初始點有一個在隊列裡
while(!q.empty())
{
node t = q.front();
q.pop();
if(num[t.x][t.y]> 1)//如果在隊列裡不隻有1個這個點，而且最後那個mv值才是最大的，是以這個直接pop掉不要了
{
num[t.x][t.y]--;
continue;
}
num[t.x][t.y]--;//如果過了前邊的判斷條件不比1大，說明這就是最後那個
node temp;
for(int i = 0;i< 4;i++)
{
int tx = t.x+book[i][0];
int ty = t.y+book[i][1];
if(flag[tx][ty]||tx> n||tx< 1||ty> m||ty< 1)//注意第一個條件
continue;
if(map[tx][ty] == '#')
continue;
if(map[tx][ty] == 'Y')
continue;
if(map[tx][ty] == '.')
{
if(vis[t.x][t.y]-1< vis[tx][ty])//隻有将要到達的點到這個點後的mv值比現在的mv值大才能替代
continue;
omap[tx][ty] = '*';//标記為*
if(vis[t.x][t.y]-1 == 0)//如果到這一點沒能量了就不用壓進隊列裡了
{
flag[tx][ty] = 1;
continue;
}
vis[tx][ty] = vis[t.x][t.y]-1; //更新最大值
temp.x = tx;
temp.y = ty;
flag[tx][ty] == 1;//标記為1
if(enemy(tx,ty))//判斷周圍有沒有E，沒有的話才能壓進隊列
{
q.push(temp);
num[tx][ty]++;
}
continue;
}
if(map[tx][ty] == 'T')//道理同上
{
if(vis[t.x][t.y]-2< vis[tx][ty])
continue;
omap[tx][ty] = '*';
if(vis[t.x][t.y]-2 == 0)
{
flag[tx][ty] == 1;
continue;
}
vis[tx][ty] = vis[t.x][t.y]-2;
temp.x = tx;
temp.y = ty;
flag[tx][ty] == 1;
if(enemy(tx,ty))
{
q.push(temp);
num[tx][ty]++;
}
continue;
}
if(map[tx][ty] == 'R')
{
if(vis[t.x][t.y]-3< vis[tx][ty])
continue;
omap[tx][ty] = '*';
if(vis[t.x][t.y]-3 == 0)
{
flag[tx][ty] == 1;
continue;
}
vis[tx][ty] = vis[t.x][t.y]-3;
temp.x = tx;
temp.y = ty;
flag[tx][ty] == 1;
if(enemy(tx,ty))
{
q.push(temp);
num[tx][ty]++;
}
continue;
}
if(map[tx][ty] == 'P')
{
if(vis[t.x][t.y]-1< vis[tx][ty])
continue;
if(vis[t.x][t.y]-1 == 0)
{
flag[tx][ty] == 1;
continue;
}
vis[tx][ty] = vis[t.x][t.y]-1;
temp.x = tx;
temp.y = ty;
flag[tx][ty] == 1;
if(enemy(tx,ty))
{
q.push(temp);
num[tx][ty]++;
}
continue;
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(vis,0,sizeof(vis));
memset(omap,0,sizeof(omap));
memset(flag,0,sizeof(flag));
memset(num,0,sizeof(num));
memset(map,0,sizeof(map));
int sx,sy;
scanf("%d %d %d",&n,&m,&sum);
getchar();//注意此處
for(int i = 1;i<= n;i++)
{
for(int j = 1;j<= m;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j] == 'Y')
sx = i,sy = j;
}
getchar();//注意此處
}
bfs(sx,sy);
for(int i = 1;i<= n;i++)
{
for(int j = 1;j<= m;j++)
{
if(omap[i][j] == '*')
printf("*");
else
printf("%c",map[i][j]);
}
printf("\n");
}
printf("\n");
}
return 0;
}
隻要是想的明白就能做出來，如果想的明白用優先隊列就更能明白了。（這個題用優先隊列真是精妙至極！）
①優先隊列可以保證每次行動的都是mv值最大的那個，也就是根本不用去維護每個點的最大mv值
②所有點隻需要走一遍，标記一下下次走到這裡直接continue
太精秒了！
上代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
typedef long long ll;
char map[105][105];
char omap[105][105];
int flag[105][105];//記錄走沒走過
int n,m,sum;
int book[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
typedef struct
{
int mv;
int x;
int y;
} node;
bool operator < (node a,node b)
{
return a.mv< b.mv;
}
bool enemy(int x,int y)//判斷周圍是否有E
{
int j;
for(j = 0;j< 4;j++)
{
int txx = x+book[j][0];
int tyy = y+book[j][1];
if(map[txx][tyy] == 'E')
{
flag[x][y] = 1;
break;
}
}
if(j == 4)
return 1;
else
return 0;
}
priority_queue<node> q;
void bfs(int sx,int sy)
{
node s;
s.x = sx;
s.y = sy;
s.mv = sum;
q.push(s);
flag[sx][sy] = 1;
while(!q.empty())
{
node t = q.top();
q.pop();
node temp;
for(int i = 0;i< 4;i++)
{
int tx = t.x+book[i][0];
int ty = t.y+book[i][1];
if(flag[tx][ty]||tx> n||tx< 1||ty> m||ty< 1)
continue;
if(map[tx][ty] == '.')
{
if(t.mv-1< 0)
continue;
omap[tx][ty] = '*';
if(t.mv-1 == 0)
continue;
temp.x = tx;
temp.y = ty;
temp.mv = t.mv-1;
flag[tx][ty] = 1;
if(enemy(tx,ty))
q.push(temp);
continue;
}
if(map[tx][ty] == 'T')
{
if(t.mv-2< 0)
continue;
omap[tx][ty] = '*';
if(t.mv-2 == 0)
continue;
temp.x = tx;
temp.y = ty;
temp.mv = t.mv-2;
flag[tx][ty] = 1;
if(enemy(tx,ty))
q.push(temp);
continue;
}
if(map[tx][ty] == 'R')
{
if(t.mv-3< 0)
continue;
omap[tx][ty] = '*';
if(t.mv-3 == 0)
continue;
temp.x = tx;
temp.y = ty;
temp.mv = t.mv-3;
flag[tx][ty] = 1;
if(enemy(tx,ty))
q.push(temp);
continue;
}
if(map[tx][ty] == 'P')
{
if(t.mv-1<= 0)
continue;
if(t.mv-1 == 0)
continue;
temp.x = tx;
temp.y = ty;
temp.mv = t.mv-1;
flag[tx][ty] = 1;
if(enemy(tx,ty))
q.push(temp);
continue;
}
if(map[tx][ty] == '#')
continue;
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(omap,0,sizeof(omap));
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag));
int sx,sy;
scanf("%d %d %d",&n,&m,&sum);
getchar();
for(int i = 1;i<= n;i++)
{
for(int j = 1;j<= m;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j] == 'Y')
sx = i,sy = j;
}
getchar();
}
bfs(sx,sy);
for(int i = 1;i<= n;i++)
{
for(int j = 1;j<= m;j++)
{
if(omap[i][j] == '*')
printf("*");
else
printf("%c",map[i][j]);
}
printf("\n");
}
printf("\n");
}
return 0;
}
ACM好題心得
![POJ 1284 Primitive Roots (歐拉函數&原根定理)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)